Approximating Max Cut with Limited Unbalance

DOI10.1016/J.ENDM.2006.06.086zbMATH Open1134.90518OpenAlexW1979140991MaRDI QIDQ3439482FDOQ3439482

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

semidefinite programmingapproximabilitylimited unbalanceMax Cut

Mathematics Subject Classification ID

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

Cites Work

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

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)