An effective compact formulation of the max cut problem on sparse graphs

DOI10.1016/J.ENDM.2011.05.020MaRDI QIDQ2840693zbMATH OpenOpenAlexFDO

Authors Giuseppe Lancia, Paolo Serafini

Publication date 23 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2011.05.020

zbMATH Keywords

max cut problemintersecting cuts and circuitsodd circuits. sparse graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• An exact algorithm for MAX-CUT in sparse graphs
• A mixed integer model for the sparsest cut problem
• A novel formulation of the max-cut problem and related algorithm
• Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
• Improved compact formulations for a wide class of graph partitioning problems in sparse graphs

Cites work

• scientific article; zbMATH DE number 780784 (Why is no real title available?)
• Compact optimization can outperform separation: a case study in structural proteomics
• Compact vs. exponential-size LP relaxations
• Encyclopedia of Algorithms
• Experiments in quadratic 0-1 programming
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(8)

• A mixed integer model for the sparsest cut problem
• Local search inequalities
• Reduced-size formulations for metric and cut polyhedra in sparse graphs
• Improved compact formulations for metric and cut polyhedra
• Deriving compact extended formulations via LP-based separation techniques
• An extended formulation for the 1‐wheel inequalities of the stable set polytope
• Deriving compact extended formulations via LP-based separation techniques
• McSparse: exact solutions of sparse maximum cut and sparse unconstrained binary quadratic optimization problems

This page was built for publication: An effective compact formulation of the max cut problem on sparse graphs

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