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

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

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[2]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[3]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[4]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[5]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[6]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[7]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[8]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463

[9]

Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397

[10]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401

[11]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151

[12]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261

[13]

Ka Luen Cheung, Man Chun Leung. Asymptotic behavior of positive solutions of the equation $ \Delta u + K u^{\frac{n+2}{n-2}} = 0$ in $IR^n$ and positive scalar curvature. Conference Publications, 2001, 2001 (Special) : 109-120. doi: 10.3934/proc.2001.2001.109

[14]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81

[15]

José Raúl Quintero, Juan Carlos Muñoz Grajales. On the existence and computation of periodic travelling waves for a 2D water wave model. Communications on Pure & Applied Analysis, 2018, 17 (2) : 557-578. doi: 10.3934/cpaa.2018030

[16]

A. Kochergin. Well-approximable angles and mixing for flows on T^2 with nonsingular fixed points. Electronic Research Announcements, 2004, 10: 113-121.

[17]

Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1

[18]

Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090

[19]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[20]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]