Randomisation achieves polylog(k)-competitiveness for k-server on every metric, independent of the space size. Best known bounds still depend on n; the k-only bound is open.
The Problems
Not schoolwork — the questions that resisted Erdős, Hilbert, and everyone since. The club keeps three shelves: what is still open, what AI recently settled, and what took humanity centuries.
Tagged online-algorithms — 2 entries. Clear
Serve requests arriving online with k mobile servers at minimum movement cost. Can any deterministic algorithm achieve k-competitiveness against the optimal offline server placement on EVERY metric space?