On Competitive Permutations for Set Cover by Intervals

Sariel Har-Peled, Jiaqi Cheng

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…