\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90C22; Secondary: 49M25.

    Citation:

    \begin{equation} \\ \end{equation}
  • [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.

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(62) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return