Article Contents
Article Contents

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

• 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.
Mathematics Subject Classification: Primary: 90C22; Secondary: 49M25.

 Citation:

•  [1] V. Asodi and S. Safra, On the complexity of the catalog-segmentation problem, Unpublished manuscript, 2001. [2] Y. Doids, V. Guruswami and S. Khanna, The $2$-catalog segmentation problem, in "Proceedings of SODA'' (Maryland, Baltimore), 1999, pp. 897-898. [3] U. Feige and M. Langberg, The RPR$^2$ rounding technique for semidefinte programs, Journal of Algorithms, 60 (2006), 1-23.doi: 10.1016/j.jalgor.2004.11.003. [4] A. Frieze and M. Jerrum, Improved approximation algorithms for MAX $k$-CUT and MAX BISECTION, Algorithmica, 18 (1997), 67-81.doi: 10.1007/BF02523688. [5] M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42 (1995), 1115-1145.doi: 10.1145/227683.227684. [6] E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, Random Structures & Algorithms, 20 (2002), 382-402.doi: 10.1002/rsa.10035. [7] Q. Han, Y. Ye and J. Zhang, An improved rounding method and semidefinite programming relaxation for graph partition, Mathematical Programming, 92 (2002), 509-535.doi: 10.1007/s101070100288. [8] J. Kleinberg, C. Papadimitriou and P. Raghavan, Segmentation problems, Journal of the ACM, 51 (2004), 263-280.doi: 10.1145/972639.972644. [9] D. Xu and J. Han, Approximation algorithm for max-bisection problem with the positive semidefinite relaxation, Journal of Computational Mathematics, 21 (2003), 357-366. [10] D. Xu, J. Han, Z. Huang and L. Zhang, Improved approximation algorithms for MAX-$\frac{ n }{ 2 }$-DIRECTED BISECTION and MAX-$\frac{ n }{ 2 }$-DENSE-SUBGRAPH, Journal of Global Optimization, 27 (2003), 399-410.doi: 10.1023/A:1026094110647. [11] D. Xu, Y. Ye and J. Zhang, A note on approximating the $2$-catalog segmentation problem, Working Paper, Department of Management Sciences, Henry, B. Tippie College of Business, The University of Iowa, Iowa City, IA, 52242, USA, 2002. [12] D. Xu, Y. Ye and J. Zhang, Approximating the $2$-catalog segmentation problem using semidefinite programming relaxations, Optimization Methods and Software, 18 (2003), 705-719. [13] Y. Ye, A $.699$-approximation algorithm for Max-Bisection, Mathematical Programming, 90 (2001), 101-111.doi: 10.1007/PL00011415. [14] U. Zwick, Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems, in "Proceedings of STOC'' (Atlanta, GA), 1999, pp. 679-687.