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

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

January 2012, 8(1): 117-126. doi: 10.3934/jimo.2012.8.117

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

Chenchen Wu ^1, , Dachuan Xu ^2, and Xin-Yuan Zhao ^2,

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

Received January 2011 Revised July 2011 Published November 2011

Abstract
Related Papers

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: approximation algorithm, semidefinite programming., 2-catalog segmentation problem.

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

Citation: Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117

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.

show all references

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.

[1]	Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial and Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881
[2]	Chengjin Li. Parameter-related projection-based iterative algorithm for a kind of generalized positive semidefinite least squares problem. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 511-520. doi: 10.3934/naco.2020048
[3]	Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015
[4]	Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034
[5]	Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187
[6]	Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127
[7]	Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[8]	Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial and Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521
[9]	Cristian Dobre. Mathematical properties of the regular -representation of matrix $$-algebras with applications to semidefinite programming. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 367-378. doi: 10.3934/naco.2013.3.367
[10]	Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015
[11]	Anwa Zhou, Jinyan Fan. A semidefinite relaxation algorithm for checking completely positive separable matrices. Journal of Industrial and Management Optimization, 2019, 15 (2) : 893-908. doi: 10.3934/jimo.2018076
[12]	Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $ k $-means problem with penalty. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021067
[13]	Jian Sun, Haiyun Sheng, Yuefang Sun, Donglei Du, Xiaoyan Zhang. Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021116
[14]	Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $ k $-means problem^†. Journal of Industrial and Management Optimization, 2022, 18 (1) : 411-426. doi: 10.3934/jimo.2020160
[15]	Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems and Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030
[16]	Jie Huang, Xiaoping Yang, Yunmei Chen. A fast algorithm for global minimization of maximum likelihood based on ultrasound image segmentation. Inverse Problems and Imaging, 2011, 5 (3) : 645-657. doi: 10.3934/ipi.2011.5.645
[17]	Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial and Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[18]	Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial and Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651
[19]	Thierry Horsin, Peter I. Kogut, Olivier Wilk. Optimal $L^2$-control problem in coefficients for a linear elliptic equation. II. Approximation of solutions and optimality conditions. Mathematical Control and Related Fields, 2016, 6 (4) : 595-628. doi: 10.3934/mcrf.2016017
[20]	Chuanhao Guo, Erfang Shan, Wenli Yan. A superlinearly convergent hybrid algorithm for solving nonlinear programming. Journal of Industrial and Management Optimization, 2017, 13 (2) : 1009-1024. doi: 10.3934/jimo.2016059

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Chenchen Wu Dachuan Xu Xin-Yuan Zhao
on Google Scholar
Chenchen Wu Dachuan Xu Xin-Yuan Zhao

[Back to Top]