On Competitive Permutations for Set Cover by Intervals
share
We revisit the problem of computing an optimal partial cover of points by intervals. We show that the greedy algorithm computes a permutation Π = π_1, π_2,… of the intervals that is 3/4-competitive for any prefix of k intervals. That is, for any k, the intervals π_1 ∪⋯∪π_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/ε) time, computes a cover by (1+ε)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.
READ FULL TEXT