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.

PDF file

In  APPROX 2010

Publisher  Springer Verlag

Details