k-伺服器問題（k-server problem）

想像一座城市裡有 k 輛行動維修車。求助電話一通一通進來，每通都在某個地址；電話一來，你就得派出一輛車前往該地址，並付出它行駛的距離。你看不到未來的電話，而且車一旦動了就無法「倒車回去」。你在每通電話後把各輛車停在哪裡，決定了下一通電話會有多貴。k-伺服器問題問的是：你該如何「線上」調度車輛，使總行駛距離相較於「事先知道每通電話的調度員」仍保持很小？

形式上，你有 k 個伺服器（點），住在一個度量空間（metric space）裡——任何有合理距離的場景，例如一張路網圖，甚至一條直線。一串請求點到來；對每個請求你必須把某個伺服器移到那個點上，付出移動的距離，並且永遠這樣做下去。成本是所有伺服器行進的總距離。這一個框架驚人地通用：分頁恰好是某種特殊度量上的 k-伺服器問題（「均勻」度量，其中每一頁與其他每一頁的距離都是 1），所以快取是 k-伺服器的小弟。著名的 k-伺服器猜想說：存在某個確定性線上演算法，在每個度量上都是 k-競爭的；它在許多情況下已被證明（而工作函數演算法在一般情況下是 (2k-1)-競爭的），但對「所有度量」都成立的乾淨 k 仍是這領域著名的未解難題之一。

k-伺服器問題之所以重要，是因為它是統合許多「移動與佈置」線上任務的大一統：快取、調度送貨機器人、跨伺服器管理資料副本，甚至為記憶體階層建模。它是檢驗線上演算法能與不能達成什麼的主力，也是深刻技巧（位勢函數、工作函數）被鍛造出來的地方。誠實的提醒：完整的 k-伺服器猜想歷經數十年仍未解；目前最佳的一般保證 (2k-1)-競爭，並不確知是否為緊界；而「度量空間」是有實質作用的——這些保證仰賴距離滿足三角不等式。