کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777222 | 1632576 | 2016 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A Note on Fractional Coloring and the Integrality gap of LP for Maximum Weight Independent Set
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A Note on Fractional Coloring and the Integrality gap of LP for Maximum Weight Independent Set A Note on Fractional Coloring and the Integrality gap of LP for Maximum Weight Independent Set](/preview/png/5777222.png)
چکیده انگلیسی
We prove a tight connection between two important notions in combinatorial optimization. Let G be a graph class (i.e. a subset of all graphs) and r(G)=supGâGâ¡Ïf(G)Ï(G) where Ïf(G) and Ï(G) are the fractional chromatic number and clique number of G respectively. In this note, we prove that r(G) tightly captures the integrality gap of the LP relaxation with clique constraints for the Maximum Weight Independent Set (MWIS) problem. Our proof uses standard applications of multiplicative weight techniques, so it is algorithmic: Any algorithm for rounding the LP can be turned into a fractional coloring algorithm and vice versa. We discuss immediate applications of our results in approximating the fractional chromatic number of certain classes of intersection graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 55, November 2016, Pages 113-116
Journal: Electronic Notes in Discrete Mathematics - Volume 55, November 2016, Pages 113-116
نویسندگان
Parinya Chalermsook, Daniel Vaz,