Résumé
We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vector problem in the l(2) norm. To obtain our result, we combine the latter algorithm for l(2) with geometric insights related to coverings. (C) 2021 Published by Elsevier Inc.
Détails
Titre
Approximate CVPp in time 2(0.802n)
Auteur(s)
Eisenbrand, Friedrich ; Venzin, Moritz
Publié dans
Journal Of Computer And System Sciences
Volume
124
Pages
129-139
Date
2022-03-01
Editeur
San Diego, ACADEMIC PRESS INC ELSEVIER SCIENCE
ISSN
0022-0000
1090-2724
1090-2724
Mots-clés (libres)
Autres identifiant(s)
Afficher la publication dans Web of Science
Laboratoires
DISOPT
Le document apparaît dans
Production scientifique et compétences > SB - Faculté des sciences de base > MATH - Institut de mathématiques > DISOPT - Chaire d'optimisation discrète
Production scientifique et compétences > SB - Faculté des sciences de base > Mathématiques
Publications validées par des pairs
Travail produit à l'EPFL
Articles de journaux
Publié
Production scientifique et compétences > SB - Faculté des sciences de base > Mathématiques
Publications validées par des pairs
Travail produit à l'EPFL
Articles de journaux
Publié
Date de création de la notice
2022-01-31