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

Chenchen Wu; Dachuan Xu; Xin-Yuan Zhao

doi:10.3934/jimo.2012.8.117

Article Contents

2012, Volume 8, Issue 1: 117-126. Doi: 10.3934/jimo.2012.8.117

This issue Previous Article A tropical cyclone-based method for global optimization Next Article Optimal assignment of principalship and residual distribution for cooperative R&D

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

1.
College of Science, Tianjin University of Technology, Tianjin 300384
2.
Department of Applied Mathematics, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing, 100124

Received: December 31, 2010

Revised: June 30, 2011

Published: December 2011

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C22; Secondary: 49M25.

Citation:

Related Papers

Cited by

References

[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.