Approximation Algorithm for the Maximum Interval Multi-cover Problem

Given a set of points \(\mathcal {P}\) on a line, a collection of intervals \(\mathcal {I }\) along the line, and a positive integer \(K \le |\mathcal {I }|\) , each point \(p\in \mathcal {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 \(\mathcal {I}' \subseteq \mathcal {I}\) with \(|\mathcal {I}'|\le K\) to maximize the number of fully-covered points, where a point p is fully-covered by \(\mathcal {I}'\) if it belongs to at least \(q_p\) intervals of \(\mathcal {I}'\) . In this paper, we present a \(\frac{1}{2}\) -approximation algorithm for the MaxIMC problem.