Re:Researchers achieve ‘absurdly fast’ algorithm for network...
by ekkeke on Thursday June 09, 2022 @01:36AM
(#31677903)
In this case the "greedy" algorithm was guaranteed to give the best possible flow in the network so this speedup applies to the optimal solution. I think in a lot of cases greedy algorithms are used when the alternative is an NP-hard problem like bin packing or TSP for which we might be looking at speeding up an already sub-optimal solution.
Re:Researchers achieve ‘absurdly fast’ algorithm for network...
by bainsfather on Thursday June 09, 2022 @03:08AM
(#31678356)
Can anyone recommend a 'friendly' overview of the 'calculus approach'?
The paper linked in the article from 2003/2008 has been split up into 3 rather technical articles - I was hoping for something easier that just gave me a flavour of the method.
Re:Researchers achieve ‘absurdly fast’ algorithm for network...
by amelius on Thursday June 09, 2022 @04:32AM
(#31678876)
Isn't the Quanta article supposed to be the 'friendly' overview?
Re:Researchers achieve ‘absurdly fast’ algorithm for network...
by DIARRHEA_xd on Thursday June 09, 2022 @09:45AM
(#31681062)
It's lacking. Their explanation for the greedy algo is great, less so for every other. By the end of the article, their 'explanations' degrade to speed analogies.
If I have the names right, your parent is looking for the derivation of "Optimal Power Flow", and its linearization "Linear/DC OPF".
Re:Researchers achieve ‘absurdly fast’ algorithm for network...
by pfdietz on Thursday June 09, 2022 @08:56AM
(#31680637)
There are classes of problems for which greedy algorithms are known to provide optimal solutions. An example is maximum matching on bipartite graphs. This is related to combinatorial structures called matroids (and an extension called greedoids.)
Re:Researchers achieve ‘absurdly fast’ algorithm for network...
by bringthesaas on Thursday June 09, 2022 @02:11AM
(#31678050)
Yea maybe for related problems (but not all optimization problems in general).
It looks like this solution works for a specific group of problems. So it won't be applicable to all problems that use greedy (or other) heuristics.
I wonder if it isn't possible to do this for other greedy algorithms, or algorithms which are trying to find optimal solutions through heuristics.