کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142499 | 957153 | 2012 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity results for the gap inequalities for the max-cut problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Complexity results for the gap inequalities for the max-cut problem Complexity results for the gap inequalities for the max-cut problem](/preview/png/1142499.png)
چکیده انگلیسی
We prove several complexity results about the gap inequalities for the max-cut problem, including (i) the gap-1 inequalities do not imply the other gap inequalities, unless NP= Co NP; (ii) there must exist non-redundant gap inequalities with exponentially large coefficients, unless NP= Co NP; (iii) the associated separation problem can be solved in finite (doubly exponential) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 40, Issue 3, May 2012, Pages 149-152
Journal: Operations Research Letters - Volume 40, Issue 3, May 2012, Pages 149-152
نویسندگان
Laura Galli, Konstantinos Kaparis, Adam N. Letchford,