Back to Search
Start Over
Approximate CVPp in time 20.802n.
- Source :
-
Journal of Computer & System Sciences . Mar2022, Vol. 124, p129-139. 11p. - Publication Year :
- 2022
-
Abstract
- We show that a constant factor approximation of the shortest and closest lattice vector problem in 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 in the ℓ 2 norm. To obtain our result, we combine the latter algorithm for ℓ 2 with geometric insights related to coverings. [ABSTRACT FROM AUTHOR]
- Subjects :
- *RIESZ spaces
*ALGORITHMS
*APPROXIMATION algorithms
*INTEGER programming
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 124
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 153707983
- Full Text :
- https://doi.org/10.1016/j.jcss.2021.09.006