An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation
Chenchen Wu Dachuan Xu Xin-Yuan Zhao
Journal of Industrial & Management Optimization 2012, 8(1): 117-126 doi: 10.3934/jimo.2012.8.117
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.
keywords: approximation algorithm semidefinite programming. 2-catalog segmentation problem

Year of publication

Related Authors

Related Keywords

[Back to Top]