摘要：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.
