Computational experience with a SDP-based algorithm for maximum cut with limited unbalance

DOI10.1002/net.20369zbMath1207.05180OpenAlexW2591764916MaRDI QIDQ3057151

Giulia Galbiati, Stefano Gualandi, Francesco Maffioli

Publication date: 24 November 2010

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20369

zbMATH Keywords

semidefinite programmingnetwork designrandomized approximation algorithmunbalanced maximum cut

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Semidefinite programming (90C22) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Approximation algorithms for maximum cut with limited unbalance

Uses Software

• DSDP5

Cites Work

• Approximation algorithms for maximum cut with limited unbalance
• Approximating Minimum Cut with Bounded Size
• Algorithm 875
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• Algorithms – ESA 2005
• A .699-approximation algorithm for Max-Bisection.
• Unnamed Item

This page was built for publication: Computational experience with a SDP-based algorithm for maximum cut with limited unbalance