Please use this identifier to cite or link to this item:
|Title:||A note on the 2-circulant inequalities for the max-cut problem|
Letchford, Adam N.
|Subjects:||FRASCATI::Natural sciences::Computer and information sciences|
FRASCATI::Natural sciences::Mathematics::Pure Mathematics
|Source:||Operations Research Letters|
|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.|
|Appears in Collections:||Department of Business Administration |
Files in This Item:
|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.