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


Text available via DOI:

View graph of relations

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

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNChapter (peer-reviewed)peer-review



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.