Approximation algorithms for maximum cut with limited unbalance
From MaRDI portal
Publication:2456360
DOI10.1016/j.tcs.2007.05.036zbMath1124.68117OpenAlexW1980036307MaRDI QIDQ2456360
Francesco Maffioli, Giulia Galbiati
Publication date: 18 October 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.05.036
Related Items (7)
Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis ⋮ Approximation algorithms for MAX RES CUT with limited unbalanced constraints ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ Simple probabilistic analysis to generalize bottleneck graph multi-partitioning ⋮ Computational experience with a SDP-based algorithm for maximum cut with limited unbalance ⋮ Two approximation algorithms for maximizing nonnegative weakly monotonic set functions
Cites Work
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Balancing signed graphs
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Computational experience with a SDP-based algorithm for maximum cut with limited unbalance
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Algorithms – ESA 2005
- A .699-approximation algorithm for Max-Bisection.
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Approximation algorithms for maximum cut with limited unbalance
