We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK


97% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Complexity results for the gap inequalities for...
View graph of relations

« Back

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

Research output: Contribution to journalJournal article


<mark>Journal publication date</mark>05/2012
<mark>Journal</mark>Operations Research Letters
Number of pages4
<mark>Original language</mark>English


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".

Related projects