Complexity results for the gap inequalities for the max-cut problem
Laura Galli (l.galliunibo.it)
Abstract: In 1996, Laurent and Poljak introduced an extremely general class of cutting planes for the max-cut problem, called gap inequalities. We prove several results about them, including the following: (i) there must exist non-dominated gap inequalities with gap larger than 1, unless NP = co-NP; (ii) there must exist non-dominated gap inequalities with exponentially large coefficients, unless NP = co-NP; (iii) the separation problem for gap inequalities can be solved in finite time (specifically, doubly exponential time).
Keywords: computational complexity, max-cut problem, cutting planes
Category 1: Combinatorial Optimization (Polyhedra )
Category 2: Integer Programming (Cutting Plane Approaches )
Citation: L. Galli, K. Kaparis & A.N. Letchford (2012) Complexity results for the gap inequalities for the max-cut problem. Oper. Res. Lett., 40(3), 149-152.
Entry Submitted: 07/19/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|