alt Hacker NewsExplain to me like im 5.
Replies
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.
I feel like the paper itself does a fairly good job:
> The [k-server] 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.
> The k-server conjecture states that a deterministic online algorithm can achieve competitive ratio k on every metric space.
I only had to look up what "competitive" means in this context, and wikipedia [0] had this to say about it:
> An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded.
The ratio by which this performance is bounded for a k-competitive algorithm is k (plus some constant) [1]. We can consider the analogy of k support technicians ("servers) located in different (physical) locations ("in metric space"): The conjecture/theorem states that in any metric space (Not necessarily two- or three-dimensional), there exists an online algorithm that results in travelled distances of no more than roughly k times that of the optimal distance if all requests were known in advance.
[0] https://en.wikipedia.org/wiki/Competitive_analysis_(online_a...
[1] https://www14.in.tum.de/personen/albers/papers/brics.pdf Section 1.1
I didn't understand it either, but now given the sibling posts I'll give it another shot:
Assume you have a number of hot dog vendors in a stadium, and over time randomly people get hungry and want a hot dog. One of the hot dog vendors needs to come to them, covering a certain distance, and "serve" them their hotdog. (After that, the vendor will idle around there.)
Assume there is a central controller with a radio that oversees the whole thing, noticing requests, then picks a hot dog vendor when a request comes in and sends them on the way. After the game, all the hot dog vendors together walked a certain distance: that's the cost (which of course you'd like to minimise).
Crucial question now is which hot dog vendor to pick for each request, and there are many algorithms (you could always pick the closest one, for example).
However, now comes the trick: Suppose the controller knows in advance all the requests - who will want to have a hotdog when and where. He still, anytime a request comes in, needs to pick a vendor to send them to the request. But now, knowing the entire future, the controller can make better choices, leading to a smaller total cost. (That's the offline version; getting to know the requests only "as they come in" is the online version.)
The question now is: Compare the actual cost an "online" algorithm incurs with the "super optimal" that would have been feasible with full foresight ("offline"). It was proven that, for k hotdog vendors, it is at least k times higher (that's the "competitive ratio") worst case (plus a constant). On average, the online algo can do much better, but worst case it would be at least k times worse.
Here, the authors of the paper prove the conjecture, namely that it is also at most k times higher. (So, even if an evil genius plans the sequence of requests against this algo, it can't make it more than k times worse.)