Stronger Linear Programming Relaxations of Max-Cut
David Avis, Jun Umemoto · 2002
We consider linear programming relaxations for the max cut problem in graphs, based on k- gonal inequalities. We show that the integrality ratio for random dense graphs is asymptotically 1 + 1=k and for random sparse graphs is at least 1 + 3=k. There are O(n ) k-gonal inequalities. These results generalize work by Poljak and Tuza, who gave similar results for k = 3.