| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 7543791 | Operations Research Letters | 2018 | 5 Pages |
Abstract
The max-cut problem is a much-studied NP-hard combinatorial optimisation problem. Poljak and Turzik found some facet-defining inequalities for this problem, which we call 2-circulant inequalities. Two polynomial-time separation algorithms have been found for these inequalities, but one is very slow and the other is very complicated. We present a third algorithm, which is as fast as the faster of the existing two, but much simpler.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Konstantinos Kaparis, Adam N. Letchford,