A Note on Approximating the 2-Catalog Segmentation Problem

  • Dachuan Xu
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , Short URL: https://optimization-online.org/?p=9217

    We present a $.73$-approximation algorithm for a disjoint $2$-Catalog Segmentation and $.63$-approximation algorithm for the joint version of the problem. Previously best known results are $.65$ and $.56$, respectively. The results are based on semidefinite programming and a subtle rounding method.

    Citation

    Working Paper, Department of Management Sciences, Henry, B. Tippie College of Business, The University of Iowa, Iowa City, IA, 52242, USA

    Article

    Download

    View A Note on Approximating the 2-Catalog Segmentation Problem