Remix.run Logo
zygentoma 4 hours ago

It's not really like you're 5, but the third sentence of the introduction makes it really understandable:

> The problem’s definition is simple: There are k servers located at points of a metric space. At each time step, a request arrives at a point of the metric space. An online algorithm must serve the request immediately by moving a server to the requested location, without knowledge of future requests. The goal is to minimize the total distance traveled by servers.

So metric space is anything where you can measure a distance, so you know the distances between all servers and the distance from the request to all servers. Could be direct distance, could be travel time …

Easiest to just imagine just some (eg. n=5) servers on a plane. A request pops up somewhere on the plane. Which server do you move there, such that the total distance moved by servers is as low as possible in the end after a sequence of requests.

abecedarius 26 minutes ago | parent [-]

Fair enough, but the abstract really is too opaque imo.

> The k-server conjecture states that a deterministic online algorithm can achieve competitive ratio k on every metric space.

I was like "algorithm for what?" when I knew what every one of those terms meant. Lots of things use k servers. Lots of problems involve metric spaces.