Please use this identifier to cite or link to this item:
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
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.
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 SizeFormat 
circulant-note_elsformat.pdf123,81 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.