非凸复盖问题的近似算法

APPROXIMATION ALGORITHMS FOR NONCONVEX COVERING PROBLEM

本文讨论了一维空间中的非凸复盖问题。其中复盖点所使用的每一个非凸部件,都是一维非正规环。这是个强 NP—完全问题。我们采用移动策略,给出了这类问题的一系列多项式时间近似算法。

In this paper,a nonconvex covering problem in one dimension is dis-cussed.For this problem,all the nonconvex objects used to cover pointsare one dismension nonregular rings.This problem is strongly NP-complete.Some polynomial time approximation algorithms applying the shifting stra-tegy are presented.