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

31–39 of 39 posts

Re: The k-server conjecture is true

#31

Post by Davidzheng »

jdw64 wrote: post #5

Looking at the recent discussions on Hacker News about AI solving difficult problems, it seems there are specific types of mathematical challenges where AI truly excels. It appears to be relatively good at problems where finding the initial answer is difficult, but verifying whether a candidate answer is correct is easy. In particular, AI feels very strong in matching-type problems, almost like fuzz testing. As seen…

It's honestly just good at math. Even at theory building i wouldn't put it below 90 percentile. Just on some things it's superhuman already and some not yet.

Re: The k-server conjecture is true

#33

Post by petesergeant »

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…

For the layman, does this result give us an optimal solution to problems like this? Is it easily explained?

Re: The k-server conjecture is true

#34

Post by [deleted] »

Davidzheng wrote: post #31
jdw64 wrote: post #5

Looking at the recent discussions on Hacker News about AI solving difficult problems, it seems there are specific types of mathematical challenges where AI truly excels. It appears to be relatively good at problems where finding the initial answer is difficult, but verifying whether a candidate answer is correct is easy. In particular, AI feels very strong in matching-type problems, almost like fuzz testing. As seen…

It's honestly just good at math. Even at theory building i wouldn't put it below 90 percentile. Just on some things it's superhuman already and some not yet.

[deleted]

Re: The k-server conjecture is true

#35

Post by saghm »

Anon84 wrote: post #32
saghm wrote: post #16

Earlier quoted context omitted.

Seems like jdw64 is extremely effective at identifying problems that AI is extremely effective at solving!

careers have been built on less!

Knowing how to use a new powerful tool is definitely a valuable asset. I hope that my wordplay didn't come across as downplaying that; I genuinely meant it as a compliment to them!

Re: The k-server conjecture is true

#36

Post by skilning »

FabHK wrote: post #15
gwt4life wrote: post #2

Explain to me like im 5.

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

Thank you! The "online" and "offline" terms were what was confusing me when trying to understand the conjecture. As a career-long software and networking person, I had a preconception of the terms that was REALLY throwing me off. :D

Re: The k-server conjecture is true

#37

Post by WhitneyLand »

petesergeant wrote: post #33
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…

For the layman, does this result give us an optimal solution to problems like this? Is it easily explained?

To answer that lets get more specific:

To buy presents for a family Christmas list Mom drives to Store A and Dad drives to Store B.

As more items get added to the list, they must decide who should drive to a new store location to buy the present. How can they minimize total driving distance while kids are randomly adding new items to their list?

The proof above guarantees its possible to never drive more than twice the mileage you would knowing all the items in advance.

The big news is this guarantee works for any number of drivers with any arrangement of gifts.

The algorithm to do this was already known, what we’ve learned is it’s not possible to do any better.

Re: The k-server conjecture is true

#38

Post by podocarp »

gumby wrote: post #9
jdw64 wrote: post #5

Looking at the recent discussions on Hacker News about AI solving difficult problems, it seems there are specific types of mathematical challenges where AI truly excels. It appears to be relatively good at problems where finding the initial answer is difficult, but verifying whether a candidate answer is correct is easy. In particular, AI feels very strong in matching-type problems, almost like fuzz testing. As seen…

> appears to be relatively good at problems where finding the initial answer is difficult, but verifying whether a candidate answer is correct is easy. The opposite can happen too, as Knuth’s recent experience showed. The system suggested an unusual approach that he explored.

Lol someone is down voting all negative comments including this one. Hilarious.

Re: The k-server conjecture is true

#39

Post by podocarp »

skilning wrote: post #36
FabHK wrote: post #15

Earlier quoted context omitted.

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

Thank you! The "online" and "offline" terms were what was confusing me when trying to understand the conjecture. As a career-long software and networking person, I had a preconception of the terms that was REALLY throwing me off. :D

Yes I hate it too, but it's common in computing too. Better terms are "on demand" and "batch" which you sometimes see used instead in other contexts.
Post reply on HN