Researchers at ETH Zurich develop the fastest possible flow algorithm
Researchers at ETH Zurich developed a groundbreaking algorithm for maximum flow computation, minimizing transport costs at high speed. Led by Rasmus Kyng, the algorithm handles diverse networks efficiently, advancing theoretical computer science significantly.
Read original article
Researchers at ETH Zurich have developed a groundbreaking algorithm that computes the maximum flow in a network while minimizing transport costs at an unprecedented speed. Led by Rasmus Kyng, the team's algorithm can efficiently handle various types of networks, including rail, road, water, and the internet. This achievement marks a significant advancement in theoretical computer science, addressing a problem that has puzzled researchers for nearly a century. Kyng's algorithm not only outperforms previous methods but also paves the way for computing optimal flows in dynamically changing networks, such as those found in biology or transportation systems. By combining innovative strategies, the team has created an almost-linear-time algorithm that revolutionizes how computers tackle complex tasks. Their work has garnered recognition in the scientific community and promises a new era of fast and efficient network flow computations.
Related
Factorio Fluids 2.0
The Factorio Friday Facts detail the game's fluid system overhaul. The new algorithm simplifies fluid flow with segments, improving efficiency, throughput, and distribution while addressing previous issues. Sacrificing realism for gameplay, the update aims to enhance player experience.
Finnish startup says it can speed up any CPU by 100x
A Finnish startup, Flow Computing, introduces the Parallel Processing Unit (PPU) chip promising 100x CPU performance boost for AI and autonomous vehicles. Despite skepticism, CEO Timo Valtonen is optimistic about partnerships and industry adoption.
Compressing graphs and indexes with recursive graph bisection (2016)
Graph reordering is applied to boost compression in graphs and indexes. A new compression-friendly technique using recursive graph bisection shows improved rates for large-scale graphs, enhancing storage and processing efficiency.
Researchers run high-performing LLM on the energy needed to power a lightbulb
Researchers at UC Santa Cruz developed an energy-efficient method for large language models. By using custom hardware and ternary numbers, they achieved high performance with minimal power consumption, potentially revolutionizing model power efficiency.
Moving objects precisely with sound
EPFL researchers use soundwaves for precise object manipulation, advancing drug delivery. Wave momentum shaping navigates objects in dynamic environments, offering noninvasive biomedical applications and potential for micro-level cell manipulation. Nature Physics publication showcases groundbreaking research.
15 commentsIn 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-...
From O(mn) to O(m) ... thus excluding N (number of vertices) from computation ...
Too good to be true?
TFA didn’t describe Kyng’s breakthrough in terms of this mscore it considers so important. What’s up with that?
https://news.ycombinator.com/item?id=31675015 (72 comments)
o(n) seems like a stronger statement to me than O(n), since all o(n) algorithms are O(n), but the reverse is not true.
Also if o(n) applies to all n, however small, whereas O(n) applies only when n -> inf,
(From the Wikipedia page example: 2n = O(n) but 2n != o(n))
Then doesn’t that means this algorithm should be applicable to even small n’s? Then it would be the opposite of a galactic algorithm, as someone above suggested, wouldn’t it?
Or am I missing something?
Solving a problem for computational efficiency is pointless.
Wy
Take a look at AI neural networks where they blast computational resources.
May be
One day this might help.
Reply to myself
Appreciate this post. And get back to writing.
Appreciation
Out of so many other less interesting post, this post caught my attention and nowhere it spoke about how it works, most importantly why it is needed.
Related
Factorio Fluids 2.0
The Factorio Friday Facts detail the game's fluid system overhaul. The new algorithm simplifies fluid flow with segments, improving efficiency, throughput, and distribution while addressing previous issues. Sacrificing realism for gameplay, the update aims to enhance player experience.
Finnish startup says it can speed up any CPU by 100x
A Finnish startup, Flow Computing, introduces the Parallel Processing Unit (PPU) chip promising 100x CPU performance boost for AI and autonomous vehicles. Despite skepticism, CEO Timo Valtonen is optimistic about partnerships and industry adoption.
Compressing graphs and indexes with recursive graph bisection (2016)
Graph reordering is applied to boost compression in graphs and indexes. A new compression-friendly technique using recursive graph bisection shows improved rates for large-scale graphs, enhancing storage and processing efficiency.
Researchers run high-performing LLM on the energy needed to power a lightbulb
Researchers at UC Santa Cruz developed an energy-efficient method for large language models. By using custom hardware and ternary numbers, they achieved high performance with minimal power consumption, potentially revolutionizing model power efficiency.
Moving objects precisely with sound
EPFL researchers use soundwaves for precise object manipulation, advancing drug delivery. Wave momentum shaping navigates objects in dynamic environments, offering noninvasive biomedical applications and potential for micro-level cell manipulation. Nature Physics publication showcases groundbreaking research.