12,000

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

93%

93% 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

Published

Journal publication date05/2012
JournalOperations Research Letters
Journal number3
Volume40
Number of pages4
Pages149-152
Original languageEnglish

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