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

DOI10.3934/JIMO.2012.8.117MaRDI QIDQ2358849zbMATH OpenOpenAlexFDO

Authors Xinyuan Zhao, Chenchen Wu, Dachuan Xu

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

2-catalog segmentation problemapproximation algorithmsemidefinite programming

Mathematics Subject Classification ID

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

Recommendations

• Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
• Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
• scientific article; zbMATH DE number 1305507
• Quasi-random PCP and hardness of 2-catalog segmentation
• Approximation algorithms for max cut and max bisection problems using semidefinite programming relaxations

Cites work

• A .699-approximation algorithm for Max-Bisection.
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• An improved rounding method and semidefinite programming relaxation for graph partition
• Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
• scientific article; zbMATH DE number 2063458 (Why is no real title available?)
• Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
• 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
• Segmentation problems
• The RPR2 rounding technique for semidefinite programs

Cited in

(3)

• 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
• Approximating the 2-catalog segmentation problem using semidefinite programming relaxations

Describes a project that uses

Uses Software

• Outward rotations

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

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