Approximating the 2-catalog segmentation problem using semidefinite programming relaxations

DOI10.1080/10556780310001634082zbMath1154.90564OpenAlexW2065554317MaRDI QIDQ4650629

Yinyu Ye, Da-Chuan Xu, Jia-Wei Zhang

Publication date: 18 February 2005

Published in: Optimization Methods and Software (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Related Items (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 ⋮ A continuation algorithm for max-cut problem ⋮ 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

Cites Work

• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
• An improved rounding method and semidefinite programming relaxation for graph partition
• A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Outward rotations
• Relations between average case complexity and approximation complexity
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization

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