1. Department of Applied Mathematics, University of Electronic Science and Technology of China, Chengdu 610054, PRC 2. Department of mathematics of Faculty of Science, Xi'an Jiaotong University, Xi'an 710049, PRC
Abstract:
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.