Please use this identifier to cite or link to this item:
https://ruomo.lib.uom.gr/handle/7000/1804
Title: | Generalised 2-circulant inequalities for the max-cut problem |
Authors: | Kaparis, Konstantinos Letchford, Adam N. Mourtos, Ioannis |
Type: | Article |
Subjects: | FRASCATI::Natural sciences::Computer and information sciences |
Keywords: | Max-cut problem Polyhedral combinatorics Cutting planes |
Issue Date: | 2022 |
Source: | Operations Research Letters |
Volume: | 50 |
Issue: | 2 |
First Page: | 122 |
Last Page: | 128 |
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. |
URI: | https://doi.org/10.1016/j.orl.2022.01.005 https://ruomo.lib.uom.gr/handle/7000/1804 |
ISSN: | 0167-6377 |
Other Identifiers: | 10.1016/j.orl.2022.01.005 |
Appears in Collections: | Department of Business Administration |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
ORL-D-21-208-R2.pdf | 149,88 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License