Contraction-based separation and lifting for solving the max-cut problem

MaRDI QIDQ3094163zbMATH OpenFDO

Authors Thorsten Bonato

Publication date 21 October 2011

Full work available at URL http://archiv.ub.uni-heidelberg.de/volltextserver/volltexte/2011/12289/

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The maximum cut problem
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• Computational study of a branching algorithm for the maximum \(k\)-cut problem
• A branch-and-bound algorithm for solving max-\(k\)-cut problem
• Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints

Cited in

(3)

• Exact solution of the 2-dimensional grid arrangement problem
• Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
• Greedy differencing edge-contraction heuristic for the max-cut problem

Describes a project that uses

Uses Software

• ABACUS
• Biq Mac

This page was built for publication: Contraction-based separation and lifting for solving the max-cut problem

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