کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141594 957034 2009 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the polyhedral lift-and-project methods and the fractional stable set polytope
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
On the polyhedral lift-and-project methods and the fractional stable set polytope
چکیده انگلیسی

We study two polyhedral lift-and-project operators (originally proposed by Lovász and Schrijver in 1991) applied to the fractional stable set polytopes. First, we provide characterizations of all valid inequalities generated by these operators. Then, we present some seven-node graphs on which the operator enforcing the symmetry of the matrix variable is strictly stronger on the odd-cycle polytope of these graphs than the operator without this symmetry requirement. This disproves a conjecture of Lipták and Tunçel from 2003.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 6, Issue 2, May 2009, Pages 206–213
نویسندگان
, ,