【摘要】 研究了相等的双目录分割问题,给出了此问题的随机算法.通过分析算法的性能,得到算法的近似性能比为0.637 8.在回答Jon Kleinberg于1998年提出的一个公开问题方面取得了一定进展.更多还原

【Abstract】 In this paper an improved randomized algorithm of the equivalent 2-catalog segmentation problem is presented. Some progresses to answer the open problem are made by analyzing this algorithm with performance guarantee. A 0.6378-approximation for the equivalent 2-catalog segmentation problem is (obtained.)更多还原