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

Electronic data

Links

Text available via DOI:

View graph of relations

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

Research output: Contribution to journalJournal article

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
<mark>State</mark>Published
<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".