کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430520 688019 2006 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hardness of approximating the Shortest Vector Problem in high ℓp norms
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Hardness of approximating the Shortest Vector Problem in high ℓp norms
چکیده انگلیسی

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-ε.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 72, Issue 2, March 2006, Pages 206-219