Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The k-server conjecture is true

arxiv.org

Post reply on HN
Print view View original

21–30 of 39 posts

Re: The k-server conjecture is true

#21

Post by saghm »

fxwin wrote: post #19
saghm wrote: post #17

Earlier quoted context omitted.

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

I take ELI5 in hackernews comments to mean: "Explain like i'm someone with a vaguely technical background but no knowledge in this particular field", not "I'm a literal five year old". I think it's probably close to impossible to explain this adequately to an actual five year old while staying true to the essence of the paper.

I would expect someone commenting ELI5 on Hacker News to mean that they didn't understand the article directly, so pasting several paragraphs verbatim is not particularly helpful to them. If you think that the article is clear, and they're still asking for clarification, it's a sign that you've probably overestimated the clarity to someone with less experience in the subject (as always, relevant xkcd for this: https://xkcd.com/2501/)

Re: The k-server conjecture is true

#22

Post by fofoz »

What memories! The proof of the WFA algorithm's (2k-1)-competitiveness for this problem was one of the papers I spent sleepless nights poring over during university. I am truly thrilled to see the k-competitiveness conjecture resolved!

Re: The k-server conjecture is true

#23

Post by WhitneyLand »

This is an important result, sometimes called the holy grail of competitive analysis.

One way to think about competitive analysis is bulk discounts. In life we’re constantly having to choose between quantity and discount. We could buy 1 item for a higher price, or say quantity 5 or 10 to get better discounts. The problem comes when we don’t know in advance exactly how many we’re going to need.

What should be our strategy for choosing how many to buy, and whatever the strategy is how well does it compare with having perfect knowledge upfront?

Re: The k-server conjecture is true

#24

Post by fxwin »

saghm wrote: post #21
fxwin wrote: post #19

Earlier quoted context omitted.

I take ELI5 in hackernews comments to mean: "Explain like i'm someone with a vaguely technical background but no knowledge in this particular field", not "I'm a literal five year old". I think it's probably close to impossible to explain this adequately to an actual five year old while staying true to the essence of the paper.

I would expect someone commenting ELI5 on Hacker News to mean that they didn't understand the article directly, so pasting several paragraphs verbatim is not particularly helpful to them. If you think that the article is clear, and they're still asking for clarification, it's a sign that you've probably overestimated the clarity to someone with less experience in the subject (as always, relevant xkcd for this: https:…

That's fair, I had assumed they hadn't read the article at all ;) If they have, it would have been nice to know which parts of the problem definition the paper describes as "simple" they struggled with, otherwise I default to "I haven't read the article and would like a summary for a technically inclined layman"

Re: The k-server conjecture is true

#26

Post by saghm »

fxwin wrote: post #24
saghm wrote: post #21

Earlier quoted context omitted.

I would expect someone commenting ELI5 on Hacker News to mean that they didn't understand the article directly, so pasting several paragraphs verbatim is not particularly helpful to them. If you think that the article is clear, and they're still asking for clarification, it's a sign that you've probably overestimated the clarity to someone with less experience in the subject (as always, relevant xkcd for this: https:…

That's fair, I had assumed they hadn't read the article at all ;) If they have, it would have been nice to know which parts of the problem definition the paper describes as "simple" they struggled with, otherwise I default to "I haven't read the article and would like a summary for a technically inclined layman"

I would expect someone who says ELI5 to have found pretty much all of it hard to understand. The paper calling something "simple" is either them talking to other experts or an instance of the same phenomenon I called out where experts vastly underestimate how approachable things are to non-expert. At least personally, I had never heard the term "metric space" before. I assumed it didn't mean "three dimensional space measured in units that are an exponent of meters", but I didn't know how to tell the difference between whether it was a specific nuanced mathematical concept or if it just meant "space that can be measured". I could google it, but when I have to do that before I've gotten through the first sentence that the paper describes as "simple", it does not give me any confidence that the paper is written with an audience like me in mind.

Re: The k-server conjecture is true

#27

Post by adw »

fn-mote wrote: post #10
fxwin wrote: post #6

Earlier quoted context omitted.

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 b…

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.

I’d be shocked if anyone with any kind of post-secondary education in any numerate discipline couldn’t give you at least an informal definition of a metric space. Certainly all the physicists, all the geneticists, all the ML people.

Re: The k-server conjecture is true

#28

Post by emil-lp »

WhitneyLand wrote: post #23

This is an important result, sometimes called the holy grail of competitive analysis. One way to think about competitive analysis is bulk discounts. In life we’re constantly having to choose between quantity and discount. We could buy 1 item for a higher price, or say quantity 5 or 10 to get better discounts. The problem comes when we don’t know in advance exactly how many we’re going to need. What should be our stra…

Or while waiting for the bus: if it's late, when should you start walking instead?

Re: The k-server conjecture is true

#30

Post by abecedarius »

zygentoma wrote: post #4
gwt4life wrote: post #2

Explain to me like im 5.

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…

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.

Post reply on HN