Improving Integrality Gaps via Chvatal-Gomory Rounding

In this work, we study the strength of the Chvatal-Gomory cut generating procedure for several hard optimization problems. For hypergraph matching on $k$-uniform hypergraphs, we show that using Chvatal-Gomory cuts of low rank can reduce the integrality gap significantly even though Sherali-Adams relaxation has a large gap even after linear number of rounds. On the other hand, we show that for other problems such as $k$-CSP, unique label cover, maximum cut, and vertex cover, the integrality gap remains large even after adding all Chvatal-Gomory cuts of large rank.

full_version_gaps_for_cg_rounding-6-15.pdf
PDF file

In  APPROX 2010

Publisher  Springer Verlag

Details

TypeInproceedings
> Publications > Improving Integrality Gaps via Chvatal-Gomory Rounding