کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142169 | 957135 | 2014 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A semidefinite approach to the Ki-cover problem
ترجمه فارسی عنوان
یک رویکرد نیمه کامل به مسئله کی-پوشش
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We apply theta body relaxations to the Ki-cover problem and show polynomial time solvability for certain classes of graphs. In particular, we give an effective relaxation where all Ki-p-hole facets are valid, and study its relation to an open question of Conforti et al. For the triangle free problem, we show for Kn that the theta body relaxations do not converge by (nâ2)/4 steps; we also prove for all G an integrality gap of 2 for the second theta body.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 42, Issue 2, March 2014, Pages 156-160
Journal: Operations Research Letters - Volume 42, Issue 2, March 2014, Pages 156-160
نویسندگان
João Gouveia, James Pfeiffer,