非凸复盖问题的近似算法

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