The k-server conjecture is true

(arxiv.org)

15 points by iamsyr3 hours ago

3 comments

  • jdw6430 minutes ago
    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.<p>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&#x27;s conversations, it has a massive advantage in rapidly substituting and testing various models.<p>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.<p>Perhaps the unsolved problems I mentioned will be cracked in the near future? It is fascinating.
    • pyentropy28 minutes ago
      &gt; Hadamard matrix of order 668<p>Solved? <a href="https:&#x2F;&#x2F;epoch.ai&#x2F;frontiermath&#x2F;open-problems&#x2F;hadamard" rel="nofollow">https:&#x2F;&#x2F;epoch.ai&#x2F;frontiermath&#x2F;open-problems&#x2F;hadamard</a>
  • gwt4life45 minutes ago
    Explain to me like im 5.
    • zygentoma34 minutes ago
      It&#x27;s not really like you&#x27;re 5, but the third sentence of the introduction makes it really understandable:<p>&gt; 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.<p>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 …<p>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.
    • fxwin30 minutes ago
      I feel like the paper itself does a fairly good job:<p>&gt; 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.<p>&gt; The k-server conjecture states that a deterministic online algorithm can achieve competitive ratio k on every metric space.<p>I only had to look up what &quot;competitive&quot; means in this context, and wikipedia [0] had this to say about it:<p>&gt; An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm&#x27;s performance—is bounded.<p>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 (&quot;servers) located in different locations (in metric space): The conjecture&#x2F;theorem states that in <i>any</i> 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.<p>[0] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Competitive_analysis_(online_algorithm)" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Competitive_analysis_(online_a...</a><p>[1] <a href="https:&#x2F;&#x2F;www14.in.tum.de&#x2F;personen&#x2F;albers&#x2F;papers&#x2F;brics.pdf" rel="nofollow">https:&#x2F;&#x2F;www14.in.tum.de&#x2F;personen&#x2F;albers&#x2F;papers&#x2F;brics.pdf</a> Section 1.1
  • jdw6440 minutes ago
    Wow, so AI can actually help with difficult problems like this. If that&#x27;s really true, I mean. Lately I&#x27;ve been feeling that the ability to choose the right problem matters a lot. It&#x27;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?<p>But it&#x27;s really fascinating.