کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657696 | 690550 | 2005 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A new algorithm for optimal 2-constraint satisfaction and its implications
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Our approach also yields connections between the complexity of some (polynomial time) high-dimensional search problems and some NP-hard problems. For example, if there are sufficiently faster algorithms for computing the diameter of n points in â1, then there is an (2-ε)n algorithm for MAX-LIN. These results may be construed as either lower bounds on the high-dimensional problems, or hope that better algorithms exist for the corresponding hard problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 348, Issues 2â3, 8 December 2005, Pages 357-365
Journal: Theoretical Computer Science - Volume 348, Issues 2â3, 8 December 2005, Pages 357-365
نویسندگان
Ryan Williams,