کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142620 | 957158 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Rank of Handelman hierarchy for Max-Cut
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider a hierarchical relaxation, called Handelman hierarchy, for a class of polynomial optimization problems. We prove that the rank of Handelman hierarchy, if applied to a standard quadratic formulation of Max-Cut, is exactly the same as the number of nodes of the underlying graph. Also we give an error bound for Handelman hierarchy, in terms of its level, applied to the Max-Cut formulation.
► We apply Handelman hierarchy to a standard quadratic formulation of Max-Cut.
► We prove that its rank is equal to the number of nodes and give an error bound.
► Duality between the Handelman hierarchy and RLT is presented.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 39, Issue 5, September 2011, Pages 323–328
Journal: Operations Research Letters - Volume 39, Issue 5, September 2011, Pages 323–328
نویسندگان
Myoung-Ju Park, Sung-Pil Hong,