Generalised 2-circulant inequalities for the max-cut problem |
| |
| Institution: | 1. QMeDA Lab, Department of Business Administration, University of Macedonia, Thessaloniki, Greece;2. Department of Management Science, Lancaster University, Lancaster, UK;3. ELTRUN Research Lab, Department of Management Science & Technology, Athens University of Economics and Business, Athens, Greece |
| |
| Abstract: | The max-cut problem is a fundamental combinatorial optimisation problem, with many applications. Poljak and Turzik found some facet-defining inequalities for the associated polytope, which we call 2-circulant inequalities. We present a more general family of facet-defining inequalities, an exact separation algorithm that runs in polynomial time, and some computational results. |
| |
| Keywords: | Max-cut problem Polyhedral combinatorics Cutting planes |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
