Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
From MaRDI portal
Publication:2444145
DOI10.1007/s10878-012-9526-3zbMath1318.90063MaRDI QIDQ2444145
Zi Xu, Da-Chuan Xu, Dong-lei Du
Publication date: 8 April 2014
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-012-9526-3
semidefinite programming; approximation algorithm; max-bisection problem; 2-catalog segmentation problem; RPR\(^{2}\) rounding
90C27: Combinatorial optimization
Related Items
A bounded-error quantum polynomial-time algorithm for two graph bisection problems, Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
Uses Software
Cites Work
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation
- Outward rotations
- Quasi-Random PCP and Hardness of 2-Catalog Segmentation
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
- Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
- The RPR2 rounding technique for semidefinite programs
- A .699-approximation algorithm for Max-Bisection.
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item