Complexity results for the gap inequalities for the max‐cut problem

Complexity results for the gap inequalities for the max‐cut problem

0.00 Avg rating0 Votes
Article ID: iaor20123360
Volume: 40
Issue: 3
Start Page Number: 149
End Page Number: 152
Publication Date: May 2012
Journal: Operations Research Letters
Authors: , ,
Keywords: max-cut problem
Abstract:

We prove several complexity results about the gap inequalities for the max‐cut problem, including (i) the gap‐1 inequalities do not imply the other gap inequalities, unless NP=Co NP; (ii) there must exist non‐redundant gap inequalities with exponentially large coefficients, unless NP=Co NP; (iii) the associated separation problem can be solved in finite (doubly exponential) time.

Reviews

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