Approximating the 2-catalog segmentation problem using semidefinite programming relaxations

DOI10.1080/10556780310001634082MaRDI QIDQ4650629zbMATH OpenOpenAlexFDO

Authors Yinyu Ye, Dachuan Xu, Jiawei Zhang

Publication date 18 February 2005

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/10556780310001634082

Mathematics Subject Classification ID

Approximation algorithms (68W25) Semidefinite programming (90C22)

Recommendations

• An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation
• scientific article; zbMATH DE number 1305507
• An improved rounding method and semidefinite programming relaxation for graph partition
• Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
• Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix

Cites work

• A new way of using semidefinite programming with applications to linear equations mod p
• An improved rounding method and semidefinite programming relaxation for graph partition
• Approximation algorithms for maximization problems arising in graph partitioning
• Approximation of dense-n/2-subgraph and the complement of min-bisection
• 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
• Relations between average case complexity and approximation complexity
• Semidefinite relaxation and nonconvex quadratic optimization

Cited in

(9)

• 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
• Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
• Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation
• Robust solutions of uncertain complex-valued quadratically constrained programs
• A continuation algorithm for max-cut problem
• Quasi-random PCP and hardness of 2-catalog segmentation
• scientific article; zbMATH DE number 1305507 (Why is no real title available?)
• On Two Segmentation Problems

This page was built for publication: Approximating the 2-catalog segmentation problem using semidefinite programming relaxations

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