Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems

DOI10.1007/s10878-012-9526-3zbMath1318.90063OpenAlexW2063687001MaRDI 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

zbMATH Keywords

semidefinite programmingapproximation algorithmmax-bisection problem2-catalog segmentation problemRPR\(^{2}\) rounding

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ A bounded-error quantum polynomial-time algorithm for two graph bisection problems

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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.

This page was built for publication: Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems