Online interval selection on a simple chain
It is shown that a deterministic memoryless one-directional revoking algorithm achieves a competitive ratio of 0.786 on the simple chain in the random order model, which is worse than the basic greedy algorithm without revoking but better than any deterministic revoking algorithm in the adversarial model.