Groupe d’études et de recherche en analyse des décisions


Stronger Linear Programming Relaxations of Max-Cut


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(nk) k-gonal inequalities. These results generalize work by Poljak and Tuza, who gave similar results for k = 3.

, 22 pages