Stronger linear programming relaxations of max-cut

0.00 Avg rating—0 Votes

Article ID:	iaor20072075
Country:	Germany
Volume:	97
Issue:	3
Start Page Number:	451
End Page Number:	469
Publication Date:	Aug 2003
Journal:	Mathematical Programming
Authors:	Avis David, Umemoto Jun
Keywords:	graphs, networks

Abstract:

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

Reviews

Required fields are marked *. Your email address will not be published.