A note on fractional coloring and the integrality gap of LP for maximum weight independent set

DOI10.1016/j.endm.2016.10.029zbMath1356.05048OpenAlexW2555658059MaRDI QIDQ510956

Parinya Chalermsook, Daniel Vaz

Publication date: 14 February 2017

Full work available at URL: https://doi.org/10.1016/j.endm.2016.10.029

zbMATH Keywords

linear programmingfractional coloringmaximum weight independent set

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Cites Work

• Approximation algorithms for maximum independent set of pseudo-disks
• On the chromatic number of multiple interval graphs and overlap graphs
• On a Coloring Problem.
• On the Shannon capacity of a graph
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on fractional coloring and the integrality gap of LP for maximum weight independent set