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

DOI10.1007/S10878-012-9526-3MaRDI QIDQ2444145zbMATH OpenOpenAlexFDO

Authors Zi Xu, Donglei Du, Dachuan Xu

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

2-catalog segmentation problemapproximation algorithmmax-bisection problemRPR\(^{2}\) roundingsemidefinite programming

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation
• Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
• scientific article; zbMATH DE number 1305507
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• scientific article; zbMATH DE number 1762086

Cites work

• A .699-approximation algorithm for Max-Bisection.
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
• scientific article; zbMATH DE number 1305507 (Why is no real title available?)
• scientific article; zbMATH DE number 2063458 (Why is no real title available?)
• scientific article; zbMATH DE number 1775433 (Why is no real title available?)
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
• Quasi-random PCP and hardness of 2-catalog segmentation
• The RPR2 rounding technique for semidefinite programs

Cited in

(6)

• Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
• An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation
• Quasi-random PCP and hardness of 2-catalog segmentation
• scientific article; zbMATH DE number 1305507 (Why is no real title available?)
• Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
• A bounded-error quantum polynomial-time algorithm for two graph bisection problems

Describes a project that uses

Uses Software

• Outward rotations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444145)