Improving Integrality Gaps via Chvatal-Gomory Rounding

  • Mohit Singh ,
  • Kunal Talwar

APPROX 2010 |

Published by Springer Verlag

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.