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


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

Home > Research > Publications & Outputs > Gap inequalities for the max-cut problem: a cut...
View graph of relations

« Back

Gap inequalities for the max-cut problem: a cutting-plane algorithm

Research output: Contribution in Book/Report/ProceedingsChapter (peer-reviewed)


Publication date2012
Host publicationCombinatorial Optimization: Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers
EditorsA.R. Mahjoub
Place of publicationBerlin
Number of pages11
ISBN (Print)978-3-642-32146-7
Original languageEnglish

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Laurent & Poljak introduced a class of valid inequalities for the max-cut problem, called gap inequalities, which include many other known inequalities as special cases. The gap inequalities have received little attention and are poorly understood. This paper presents the first ever computational results. In particular, we describe a cutting-plane scheme based on an effective heuristic separation algorithm for gap inequalities, and show that these yield extremely strong upper bounds in practice.