Approximate CVPp in time 20.802n.

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]