k servers sit on a metric space — here the integer line 0–20. Requests arrive one at a time and each must be served by moving a server onto the requested point; the cost is the total distance moved. The catch: an online algorithm must decide now, without seeing the rest of the sequence.
ALG is c-competitive if, for every request sequence σ, its cost stays
within a factor c of what a clairvoyant offline optimum would have paid:b absorbs start-up effects, so c is what matters — it is the worst-case
price of not knowing the future. Lower is better; c = 1 means matching the optimum.Greedy moves the nearest server. The adversarial sequence pokes back and forth between two points that
straddle one server while another sits idle far away: Greedy shuttles that one server forever, so its cost grows
without bound while OPT stays fixed. No constant c can hold.
Double Coverage moves both neighbours of the request toward it at equal speed, stopping when one
arrives (only the nearest server moves if all of them lie on one side). Paying double looks wasteful, but it drags
idle servers into useful territory — that is exactly what makes it k-competitive on a line. The
k-server conjecture, still open, says some algorithm is k-competitive in every metric space.
OPT here is the true offline optimum for the requests seen so far, recomputed at every step by dynamic programming over server configurations — so the ratio shown is the honest one. It may revise its whole plan when a new request arrives, which is why its servers can jump.