Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142499 | Operations Research Letters | 2012 | 4 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Laura Galli, Konstantinos Kaparis, Adam N. Letchford,