Approximating Max Cut with Limited Unbalance

DOI10.1016/J.ENDM.2006.06.086MaRDI QIDQ3439482zbMATH OpenOpenAlexFDO

Authors Giulia Galbiati, Francesco Maffioli

Publication date 29 May 2007

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

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

zbMATH Keywords

approximabilitylimited unbalanceMax Cutsemidefinite programming

Mathematics Subject Classification ID

Approximation algorithms (68W25) Semidefinite programming (90C22) Programming involving graphs or networks (90C35)

Cites work

• A .699-approximation algorithm for Max-Bisection.
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

This page was built for publication: Approximating Max Cut with Limited Unbalance

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