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

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

[4]

A. Frieze and M. Jerrum, Improved approximation algorithms for MAX $k$-CUT and MAX BISECTION,, Algorithmica, 18 (1997), 67.  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.  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.  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.  doi: 10.1007/s101070100288.  Google Scholar

[8]

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

[13]

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

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

[4]

A. Frieze and M. Jerrum, Improved approximation algorithms for MAX $k$-CUT and MAX BISECTION,, Algorithmica, 18 (1997), 67.  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.  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.  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.  doi: 10.1007/s101070100288.  Google Scholar

[8]

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

[13]

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

[1]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[2]

Karol Mikula, Jozef Urbán, Michal Kollár, Martin Ambroz, Ivan Jarolímek, Jozef Šibík, Mária Šibíková. Semi-automatic segmentation of NATURA 2000 habitats in Sentinel-2 satellite images by evolving open curves. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1033-1046. doi: 10.3934/dcdss.2020231
[3]

Karol Mikula, Jozef Urbán, Michal Kollár, Martin Ambroz, Ivan Jarolímek, Jozef Šibík, Mária Šibíková. An automated segmentation of NATURA 2000 habitats from Sentinel-2 optical data. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1017-1032. doi: 10.3934/dcdss.2020348
[4]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162
[5]

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007
[6]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122
[7]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031
[8]

Xiaoli Lu, Pengzhan Huang, Yinnian He. Fully discrete finite element approximation of the 2D/3D unsteady incompressible magnetohydrodynamic-Voigt regularization flows. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 815-845. doi: 10.3934/dcdsb.2020143
[9]

Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134
[10]

Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020389
[11]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005
[12]

Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems & Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048
[13]

Balázs Kósa, Karol Mikula, Markjoe Olunna Uba, Antonia Weberling, Neophytos Christodoulou, Magdalena Zernicka-Goetz. 3D image segmentation supported by a point cloud. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 971-985. doi: 10.3934/dcdss.2020351
[14]

Petr Pauš, Shigetoshi Yazaki. Segmentation of color images using mean curvature flow and parametric curves. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1123-1132. doi: 10.3934/dcdss.2020389
[15]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
[16]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463
[17]

Bilal Al Taki, Khawla Msheik, Jacques Sainte-Marie. On the rigid-lid approximation of shallow water Bingham. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 875-905. doi: 10.3934/dcdsb.2020146
[18]

P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178
[19]

Simone Fagioli, Emanuela Radici. Opinion formation systems via deterministic particles approximation. Kinetic & Related Models, 2021, 14 (1) : 45-76. doi: 10.3934/krm.2020048
[20]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences