2026-07-22T16:56:11Z
https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:12909
2024-03-06T10:51:03Z
ddc:004
open_access
Approximate CVP_p in Time 2^{0.802 n}
Eisenbrand, Friedrich
Venzin, Moritz
Shortest and closest vector problem
approximation algorithm
sieving
covering convex bodies
We show that a constant factor approximation of the shortest and closest lattice vector problem w.r.t. any π_p-norm can be computed in time 2^{(0.802 +Ξ΅) n}. This matches the currently fastest constant factor approximation algorithm for the shortest vector problem w.r.t. πβ. To obtain our result, we combine the latter algorithm w.r.t. πβ with geometric insights related to coverings.
Schloss Dagstuhl β Leibniz-Zentrum fΓΌr Informatik
Friedrich Eisenbrand and Moritz Venzin
2020
Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
InProceedings
Text
doc-type:ResearchArticle
publishedVersion
application/pdf
doi:10.4230/LIPIcs.ESA.2020.43
urn:nbn:de:0030-drops-129097
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.43
eng
https://creativecommons.org/licenses/by/3.0/legalcode