logoalt Hacker News

fxwintoday at 10:22 AM2 repliesview on HN

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


Replies

fn-motetoday at 11:37 AM

There’s a difference between “pretty good” and understandable.

The phrase “metric space” (more or less) disqualifies anyone without an undergraduate degree in mathematics.

Fortunately a sibling to the parent explains that.

show 2 replies
saghmtoday at 12:47 PM

I want to meet the 5 year olds who you think will easily understand all of that

show 1 reply