Partial interval multicover: Approximation and complexity

We study a variant of set cover on the real line, where elements are points, sets are intervals, and each point has an integer demand; a point is fully covered when it is contained in at least its demand many chosen intervals. The objective is to select the fewest intervals that fully cover at least a specified number of points. We present the first polynomial-time approximation scheme (PTAS) for the unweighted version of this problem and show that a natural weighted generalization is NP-complete.

Authors

• Peng Li
• Xiangzhi Tu
• Zhao Zhang Hefei University of Technology, Yunnan Key Laboratory of Software Engineering
• Yixin Cao

Keywords

• Partial cover
• Multicover
• Polynomial-time approximation scheme
• Dynamic programming
• NP-completeness