hBccatalog segmentation

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 ,

    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. CitationWorking Paper, Department of Management Sciences, Henry, B. Tippie College of Business, The University … Read more