The k-server conjecture is true
The k-server conjecture states that a deterministic online algorithm can achieve competitive ratio k on every metric space. We prove the conjecture. Specifically, we show that the work function algorithm satisfies it. Our proof uses a natural algebraic representation of the work function as a matrix, which encodes all feasible paths to reach a configuration. In this representation, the minimum and addition operations arising in the definition of optimal costs correspond to addition and multiplication of formal expressions, and each work function value corresponds to the determinant of k columns of the matrix. A request arrival updates the representation via a change of basis and row replacement. The amortized analysis is based on a potential function defined in terms of a larger matrix whose coordinates are pairs of coordinates of the original matrix representation.
- 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?
- 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!
- JohnKemeny
> The second author, Elias Koutsoupias, dedicates this work to his constant friends Amos Fiat, Anna Karlin, and Christos Papadimitriou.
I wonder what Papadimitriou thinks about getting dedicated LLM generated proofs.
- jdw64
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 in Terence Tao's conversations, it has a massive advantage in rapidly substituting and testing various models.
Given these strengths, I feel it would be highly effective for problems like the Hadamard matrix of order 668, the Lonely Runner conjecture, and the Graceful Tree conjecture.
Perhaps the unsolved problems I mentioned will be cracked in the near future? It is fascinating.
- jdw64
Wow, so AI can actually help with difficult problems like this. If that's really true, I mean. Lately I've been feeling that the ability to choose the right problem matters a lot. It's a game where the people who use AI to stake out these problems first have the advantage—so of course the people who were sustained by scientific discussion and community knowledge transfer would feel sad about it, right?
But it's really fascinating.