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

چکیده انگلیسی
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
Journal: Journal of Computer and System Sciences - Volume 72, Issue 2, March 2006, Pages 206-219