The k-Server Problem

Schedule the movement of k servers in a metric space M in
response to a sequence of requests Ρ of requests.

requests Ρ = r¹r² ...rⁿ, points in M

after rⁱ: move one server to rⁱ

online: decision must be made before rⁱ⁺¹ is revealed

Goal: minimize total movement cost