Institutional Repository of Academic Research
University of Macedonia
Please use this identifier to cite or link to this item:
https://ruomo.lib.uom.gr/handle/7000/684| Title: | A note on the 2-circulant inequalities for the max-cut problem |
| Authors: | Kaparis, Konstantinos Letchford, Adam N. |
| Type: | Article |
| Subjects: | FRASCATI::Natural sciences::Computer and information sciences FRASCATI::Natural sciences::Mathematics::Pure Mathematics |
| Keywords: | Max-cut problem Polyhedral combinatorics Branch-and-cut |
| Issue Date: | Jul-2018 |
| Publisher: | Elsevier |
| Source: | Operations Research Letters |
| Volume: | 46 |
| Issue: | 4 |
| First Page: | 443 |
| Last Page: | 447 |
| 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. |
| URI: | https://doi.org/10.1016/j.orl.2018.05.006 https://ruomo.lib.uom.gr/handle/7000/684 |
| ISSN: | 0167-6377 |
| Other Identifiers: | 10.1016/j.orl.2018.05.006 |
| Appears in Collections: | Department of Business Administration |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| circulant-note_elsformat.pdf | 123,81 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.