Home > Research > Publications & Outputs > Complexity results for the gap inequalities for...

Links

Text available via DOI:

View graph of relations

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

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
<mark>Journal publication date</mark>05/2012
<mark>Journal</mark>Operations Research Letters
Issue number3
Volume40
Number of pages4
Pages (from-to)149-152
Publication StatusPublished
<mark>Original language</mark>English

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.

Bibliographic note

This is the 2nd of two papers on "gap inequalities". The other, already published in OR Letters in 2011, was entitled " Gap inequalities for non-convex mixed-integer quadratic programs".