Mohit Singh and Kunal Talwar
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.
|Published in||APPROX 2010|