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.