A 1/2-approximation algorithm for maximum interval multi-cover

Given a set of points P on a line, a collection of intervals I along the line, and a positive integer K ≤ | I |, each point p ∈ P is associated with a covering requirement q p, the goal of the maximum interval multi-cover (MaxIMC) problem is to find a sub-collection of intervals I ′ ⊆ I with | I ′ | ≤ K to maximize the number of fully-covered points, where a point p is fully-covered by I ′ if it belongs to at least q p intervals of I ′. In this paper, we present a 1 2 -approximation algorithm for the MaxIMC problem.

Authors

• Yuxuan Xu
• Yingli Ran
• Zhao Zhang Hefei University of Technology, Yunnan Key Laboratory of Software Engineering

Keywords

• Maximum cover
• Multi-cover
• Dynamic programming
• Approximation ratio