American Institute of Mathematical Sciences

Advanced
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

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 & 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. Google Scholar

[2]

Y. Doids, V. Guruswami and S. Khanna, The $2$-catalog segmentation problem, in "Proceedings of SODA'' (Maryland, Baltimore), 1999, pp. 897-898. Google Scholar

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

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

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

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

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

[8]

J. Kleinberg, C. Papadimitriou and P. Raghavan, Segmentation problems, Journal of the ACM, 51 (2004), 263-280. doi: 10.1145/972639.972644.  Google Scholar

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

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

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

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

[13]

Y. Ye, A $.699$-approximation algorithm for Max-Bisection, Mathematical Programming, 90 (2001), 101-111. doi: 10.1007/PL00011415.  Google Scholar

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

show all references

References:
[1]

V. Asodi and S. Safra, On the complexity of the catalog-segmentation problem, Unpublished manuscript, 2001. Google Scholar

[2]

Y. Doids, V. Guruswami and S. Khanna, The $2$-catalog segmentation problem, in "Proceedings of SODA'' (Maryland, Baltimore), 1999, pp. 897-898. Google Scholar

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

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

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

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

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

[8]

J. Kleinberg, C. Papadimitriou and P. Raghavan, Segmentation problems, Journal of the ACM, 51 (2004), 263-280. doi: 10.1145/972639.972644.  Google Scholar

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

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

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

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

[13]

Y. Ye, A $.699$-approximation algorithm for Max-Bisection, Mathematical Programming, 90 (2001), 101-111. doi: 10.1007/PL00011415.  Google Scholar

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

[1]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2019, 15 (2) : 893-908. doi: 10.3934/jimo.2018076
[12]

Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $ k $-means problem†. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020160
[13]

Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $ k $-means problem with penalty. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021067
[14]

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 & Management Optimization, 2021  doi: 10.3934/jimo.2021116
[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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2017, 13 (2) : 1009-1024. doi: 10.3934/jimo.2016059

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (38)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences