×

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

Summary: In this paper, we consider the \(2\)-catalog segmentation problem. For the disjoint version, we propose an approximation algorithm based on the non-uniform rotation technique using a semidefinite programming (SDP) relaxation. We give the performance curve depending on the ratio between the value of optimal SDP solution and the total weight. In this curve, the lowest point implies the approximation ratio is \(0.7317\) which is the best ratio for the disjoint version until now. We also consider the performance curve of the joint version.

MSC:

90C22 Semidefinite programming
49M25 Discrete approximations in optimal control
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V. Asodi, <em>On the complexity of the catalog-segmentation problem</em>,, Unpublished manuscript (2001)
[2] Y. Doids, <em>The \(2\)-catalog segmentation problem</em>,, in, 897 (1999)
[3] U. Feige, <em>The \(RPR^2\) rounding technique for semidefinte programs</em>,, Journal of Algorithms, 60, 1 (2006) · Zbl 1113.90116 · doi:10.1016/j.jalgor.2004.11.003
[4] A. Frieze, <em>Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION</em>,, Algorithmica, 18, 67 (1997) · Zbl 0873.68078 · doi:10.1007/BF02523688
[5] M. X. Goemans, <em>Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming</em>,, Journal of the ACM, 42, 1115 (1995) · Zbl 0885.68088 · doi:10.1145/227683.227684
[6] E. Halperin, <em>A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems</em>,, Random Structures & Algorithms, 20, 382 (2002) · Zbl 1017.68089 · doi:10.1002/rsa.10035
[7] Q. Han, <em>An improved rounding method and semidefinite programming relaxation for graph partition</em>,, Mathematical Programming, 92, 509 (2002) · Zbl 1008.90042 · doi:10.1007/s101070100288
[8] J. Kleinberg, <em>Segmentation problems</em>,, Journal of the ACM, 51, 263 (2004) · Zbl 1317.90329 · doi:10.1145/972639.972644
[9] D. Xu, <em>Approximation algorithm for max-bisection problem with the positive semidefinite relaxation</em>,, Journal of Computational Mathematics, 21, 357 (2003) · Zbl 1066.90078
[10] D. Xu, <em>Improved approximation algorithms for MAX-</em>\( \frac{ n }{ 2 } \)-DIRECTED BISECTION and MAX-\( \frac{ n }{ 2 } \)-DENSE-SUBGRAPH,, Journal of Global Optimization, 27, 399 (2003) · Zbl 1046.90094 · doi:10.1023/A:1026094110647
[11] D. Xu, <em>A note on approximating the \(2\)-catalog segmentation problem</em>,, Working Paper (5224)
[12] D. Xu, <em>Approximating the \(2\)-catalog segmentation problem using semidefinite programming relaxations</em>,, Optimization Methods and Software, 18, 705 (2003) · Zbl 1154.90564
[13] Y. Ye, <em>A \(.699\)-approximation algorithm for Max-Bisection</em>,, Mathematical Programming, 90, 101 (2001) · Zbl 1059.90119 · doi:10.1007/PL00011415
[14] U. Zwick, <em>Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems</em>,, in, 679 (1999) · Zbl 1345.90064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.