An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation
Chenchen Wu, Dachuan Xu, Xinyuan Zhao · Journal of Industrial and Management Optimization · 2011
In this paper, we consider the $2$-catalog segmentation problem. Forthe disjoint version, we propose an approximationalgorithm based on the non-uniform rotation technique using asemidefinite programming ($SDP$) relaxation. We give theperformance curve depending on the ratio between the value of optimalSDP solution and the total weight. In this curve, thelowest 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.