[HN Gopher] Researchers at ETH Zurich develop the fastest possib...
       ___________________________________________________________________
        
       Researchers at ETH Zurich develop the fastest possible flow
       algorithm
        
       Author : jeroenvlek
       Score  : 152 points
       Date   : 2024-06-29 11:12 UTC (11 hours ago)
        
 (HTM) web link (ethz.ch)
 (TXT) w3m dump (ethz.ch)
        
       | squarerootof-1 wrote:
       | Where is the paper / code for this?
        
         | styluss wrote:
         | First link in "further information"
         | 
         | https://cacm.acm.org/research/almost-linear-time-algorithms-...
        
           | elwell wrote:
           | In 2030, this algorithm will be expected to optimally solve
           | some leetcode interview question.
        
       | c-smile wrote:
       | > Almost-Linear-Time Algorithm
       | 
       | From O(mn) to O(m) ... thus excluding N (number of vertices) from
       | computation ...
       | 
       | Too good to be true?
        
         | progbits wrote:
         | Constant factor so large it's going to be slower than existing
         | (asymptotically worse) algorithms on any practical inputs.
         | 
         | Still, a neat theoretical result.
        
       | Sniffnoy wrote:
       | The abstract just says the time is m^(1+o(1))... anyone know if a
       | more specific bound is stated anywhere?
        
         | Zacharias030 wrote:
         | Note that this is a ,,small o", so o(1) captures terms that
         | ,,divided by 1" go to zero as m to infinity.
         | 
         | https://de.m.wikipedia.org/wiki/Landau-Symbole
        
           | yorwba wrote:
           | English Wikipedia has an explanation, too:
           | https://en.wikipedia.org/wiki/Big_O_notation#Little-
           | o_notati...
        
         | JohnKemeny wrote:
         | It means that you can choose constants such that the algorithm
         | is as close to O(m) as you'd like.
         | 
         | In other words, it's an algorithm scheme that allows you to get
         | an algorithm running in time O(m^e) for any e>1.
        
           | Sniffnoy wrote:
           | Sorry, where's that stated? I'm pretty doubtful of that claim
           | because if that's what they meant they would say that --
           | they'd say it was O(m^(1+e)), that would be well-understood
           | notation. But what they wrote is that it's O(m^(1+o(1))),
           | which, read as written, means it's a single bound that
           | they're just not being very specific about.
           | 
           | I'm not asking for help decoding the notation; I'm asking for
           | if anyone knows what the more detailed bound is that
           | O(m^(1+o(1))) is abstracting.
        
       | nabla9 wrote:
       | The algorithm is near linear asymptotically _at the limit_ when n
       | - > inf.
       | 
       | In the end of video they tell there is no way that any
       | implementation of their algorithm gets close to beating existing
       | algorithms in the real world.
       | 
       | https://cacm.acm.org/research/almost-linear-time-algorithms-...
        
       | JohnKemeny wrote:
       | Related: https://news.ycombinator.com/item?id=31149038 (40
       | comments)
       | 
       | https://news.ycombinator.com/item?id=31675015 (72 comments)
        
       ___________________________________________________________________
       (page generated 2024-06-29 23:00 UTC)