Article ID Journal Published Year Pages File Type
430520 Journal of Computer and System Sciences 2006 14 Pages PDF
Abstract

We present a new hardness of approximation result for the Shortest Vector Problem in ℓp norm (denoted by SVPp). Assuming NP ⊈ ZPP, we show that for every ε>0, there is a constant p(ε) such that for all integers p⩾p(ε), the problem SVPp has no polynomial time approximation algorithm with approximation ratio p1-ε.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics