On Competitive Permutations for Set Cover by Intervals

Abstract

We revisit the problem of computing an optimal partial cover of points by intervals. We show that the greedy algorithm computes a permutation $\Pi ={\pi }_1,{\pi }_2,\dots$ of the intervals that is $3/4$-competitive for any prefix of $k$ intervals. That is, for any $k$, the intervals ${\pi }_1\cup \cdots \cup {\pi }_k$ covers at least $3/4$-fraction of the points covered by the optimal solution using $k$ intervals. We also provide an approximation algorithm that, in $O(n+m/\epsilon )$ time, computes a cover by $(1+\epsilon )k$ intervals that is as good as the optimal solution using $k$ intervals, where $n$ is the number of input points, and $m$ is the number of intervals (we assume here the input is presorted). Finally, we show a counter example illustrating that the optimal solutions for set cover do not have the diminishing return property -- that is, the marginal benefit from using more sets is not monotonically decreasing. Fortunately, the diminishing returns does hold for intervals.

References in corpus (1)

• Performance of a greedy algorithm for edge covering by cliques in interval graphs