An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation

DOI10.3934/JIMO.2012.8.117zbMath1364.90248OpenAlexW2327702648MaRDI QIDQ2358849

Xinyuan Zhao, Da-Chuan Xu, Chen-Chen Wu

Publication date: 16 June 2017

Published in: Journal of Industrial and Management Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3934/jimo.2012.8.117

zbMATH Keywords

semidefinite programmingapproximation algorithm2-catalog segmentation problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Discrete approximations in optimal control (49M25)

Related Items (2)

Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
• An improved rounding method and semidefinite programming relaxation for graph partition
• Outward rotations
• 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
• Segmentation problems
• A .699-approximation algorithm for Max-Bisection.

This page was built for publication: An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation