科研之友
微信
新浪微博
Facebook
分享链接
摘要
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.
- 出版日期2012-2
- 单位北京工业大学
