Online Interval Selection on a Simple Chain

Abstract

A set of intervals $I=\{I_1,I_2,\dots ,I_n\}$ forms a simple chain if, for every $2\le i\le n-1$, interval $I_i$ overlaps only with $I_{i-1}$ and $I_{i+1}$. We show that a deterministic memoryless one-directional revoking algorithm achieves a competitive ratio of $2(1-1/\sqrt{e})\approx 0.786$ on the simple chain in the random order model, hence performs worse than the basic greedy algorithm without revoking that has a competitive ratio of $(1-1/e^2)\approx 0.864$, but better than any deterministic revoking algorithm in the adversarial model that has a competitive ratio of at most $0.75$. The proof of the latter also leads to a lower bound of $n/4$ for the advice complexity.

7 pages