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

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

[2]

Y. Doids, V. Guruswami and S. Khanna, The $2$-catalog segmentation problem,, in, (1999), 897.

[3]

U. Feige and M. Langberg, The RPR$^2$ rounding technique for semidefinte programs,, Journal of Algorithms, 60 (2006), 1. 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. 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. 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. 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. doi: 10.1007/s101070100288.

[8]

J. Kleinberg, C. Papadimitriou and P. Raghavan, Segmentation problems,, Journal of the ACM, 51 (2004), 263. 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.

[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. doi: 10.1023/A:1026094110647.

[11]

D. Xu, Y. Ye and J. Zhang, A note on approximating the $2$-catalog segmentation problem,, Working Paper, (5224).

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

[13]

Y. Ye, A $.699$-approximation algorithm for Max-Bisection,, Mathematical Programming, 90 (2001), 101. 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, (1999), 679.

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, (1999), 897.

[3]

U. Feige and M. Langberg, The RPR$^2$ rounding technique for semidefinte programs,, Journal of Algorithms, 60 (2006), 1. 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. 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. 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. 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. doi: 10.1007/s101070100288.

[8]

J. Kleinberg, C. Papadimitriou and P. Raghavan, Segmentation problems,, Journal of the ACM, 51 (2004), 263. 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.

[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. doi: 10.1023/A:1026094110647.

[11]

D. Xu, Y. Ye and J. Zhang, A note on approximating the $2$-catalog segmentation problem,, Working Paper, (5224).

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

[13]

Y. Ye, A $.699$-approximation algorithm for Max-Bisection,, Mathematical Programming, 90 (2001), 101. 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, (1999), 679.

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

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

Anwa Zhou, Jinyan Fan. A semidefinite relaxation algorithm for checking completely positive separable matrices. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-16. doi: 10.3934/jimo.2018076

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008

[15]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems - A, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653

[16]

Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99

[17]

Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585

[18]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[19]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509

[20]

Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032

2017 Impact Factor: 0.994

Metrics

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

Other articles
by authors

[Back to Top]