{"id":"arxiv/2608.10376","url":"https://arxiv.org/abs/2608.10376","tags":["cs.DS","math.CO"],"score":0,"title":"Online Interval Selection on a Simple Chain","domain":"cs.DS","source":"arxiv","authors":["Yaqiao Li","Ali Mohammad Lavasani","Denis Pankratov"],"reviews":0,"subject":"cs.DS","summary":"A set of intervals $I = \\{ I_1, I_2, \\dots, I_n \\}$ forms a simple chain if, for every $2\\leq i \\leq 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-11","reactions":{}}