A Note on Approximating the 2-Catalog Segmentation Problem

Dachuan Xu (xudclsec.cc.ac.cn)
Yinyu Ye (yinyu-yeuiowa.edu)
Jiawei Zhang (jiawei-zhanguiowa.edu)

Abstract: 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.

Keywords: $2$-Catalog Segmentation, Semidefinite Programming

Category 1: Combinatorial Optimization

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Combinatorial Optimization (Approximation Algorithms )

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

Download: [Postscript]

Entry Submitted: 03/11/2002
Entry Accepted: 03/11/2002
Entry Last Modified: 03/11/2002

Modify/Update this entry