Improved Approximation Algorithms for the 2-Catalog Segmentation Problems using Semidefinite Programming Relaxations

摘要：

　　In this paper, we consider 2-catalog segmentation problems. Using the techniques of non-uniform rotation and semidefinite programming rounding, we propose an improved 0.7317-approximation algorithm for the disjoint version which can deduce a 0.6338 approximation ratio for the joint version. We also give the performance guarantee curve which depends on the input data and the optimal solution of the corresponding semidefinite programming relaxation.

关键词： 2-catalog segmentation problem Approximation algorithm Semidefinite programming

作者: Chenchen Wu Dachuan Xu Xinyuan Zhao

作者单位: Department of Applied Mathematics, Beijing University of Technology 100 Pingleyuan, Chaoyang District, Beijing 100124, China

会议类型: 国际会议

会议名称: 第8届国际最优化方法及应用大会

会议地点: 上海

会议语种:英文

页码: 370-371

在线出版日期: 2010-12-10（万方平台首次上网日期，不代表论文的发表时间）