Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Improving Integrality Gaps via Chvatal-Gomory Rounding

Mohit Singh and Kunal Talwar

Abstract

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.

Details

Publication typeInproceedings
Published inAPPROX 2010
PublisherSpringer Verlag
> Publications > Improving Integrality Gaps via Chvatal-Gomory Rounding