Please use this identifier to cite or link to this item:
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.
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 SizeFormat 
ORL-D-21-208-R2.pdf149,88 kBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons