Eisenbrand, FriedrichVenzin, Moritz2022-01-312022-01-312022-01-312022-03-0110.1016/j.jcss.2021.09.006https://infoscience.epfl.ch/handle/20.500.14299/184867WOS:000711661500002We 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.Computer Science, Hardware & ArchitectureComputer Science, Theory & MethodsComputer Sciencelattice and integer programmingalgorithmic geometry of numberssievinggeometric coveringshortest vector problemlattice vectorsalgorithmhardnesspointstext::journal::journal article::research article