IMPROVED RANDOMIZED ALGORITHM FOR THE EQUIVALENT 2-CATALOG SEGMENTATION PROBLEM ∗
Yuan Yubo, Chengxian Xu · 2005
An improved randomized algorithm of the equivalent 2-catalog segmentation problem is presented. The result obtained in this paper makes some progress to answer the open problem by analyze this algorithm with performance guarantee. A 0.6378- approximation for the equivalent 2-catalog segmentation problem is obtained.