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

DOI10.1016/j.endm.2011.05.020zbMath1268.05204OpenAlexW1994813942MaRDI QIDQ2840693

Paolo Serafini, Giuseppe Lancia

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)

Related Items (5)

Improved compact formulations for metric and cut polyhedra ⋮ An extended formulation for the 1‐wheel inequalities of the stable set polytope ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Local search inequalities ⋮ Deriving compact extended formulations via LP-based separation techniques

Cites Work

• Experiments in quadratic 0-1 programming
• Using separation algorithms to generate mixed integer model reformulations
• Compact vs. exponential-size LP relaxations
• Compact optimization can outperform separation: a case study in structural proteomics
• Encyclopedia of Algorithms
• Unnamed Item

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