Gap inequalities for the max-cut problem: a cutting-plane algorithm

DOI10.1007/978-3-642-32147-4_17MaRDI QIDQ3167623zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Laura Galli, Konstantinos Kaparis, Adam N. Letchford

Publication date 2 November 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32147-4_17

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Complexity results for the gap inequalities for the max-cut problem
• Gap inequalities for the cut polytope
• Stronger linear programming relaxations of max-cut
• Gap inequalities for non-convex mixed-integer quadratic programs
• A note on the 2-circulant inequalities for the MAX-cut problem

Cited in

(8)

• Computational study of valid inequalities for the maximum \(k\)-cut problem
• A fixed-parameter algorithm for the Max-Cut problem on embedded 1-planar graphs
• Gap inequalities for the cut polytope
• A note on the 2-circulant inequalities for the MAX-cut problem
• Generalised 2-circulant inequalities for the max-cut problem
• Gap inequalities for non-convex mixed-integer quadratic programs
• Complexity results for the gap inequalities for the max-cut problem
• The Boolean quadric polytope

This page was built for publication: Gap inequalities for the max-cut problem: a cutting-plane algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167623)