Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430520 | Journal of Computer and System Sciences | 2006 | 14 Pages |
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