G-2002-48
Stronger Linear Programming Relaxations of Max-Cut
et référence BibTeX
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.
Paru en septembre 2002 , 22 pages