3 ms·

So basically they took a greedy algorithm that used a combinatorial approach and transformed it to use a calculus approach by inspiring from a related problem o

So basically they took a greedy algorithm that used a combinatorial approach and transformed it to use a calculus approach by inspiring from a related problem of "electrical flow through a network". 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.

ekkeke 4y ago
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.
bringthesaas 4y ago
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.
bainsfather 4y ago
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.
- amelius 4y ago
  Isn't the Quanta article supposed to be the 'friendly' overview?
  - DIARRHEA_xd 4y ago
    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".
amelius 4y ago
Linear electrical networks have no maximum current, though.
pfdietz 4y ago
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.) https://en.wikipedia.org/wiki/Greedoid https://en.wikipedia.org/wiki/Greedoid

ekkeke 4y ago

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.

bringthesaas 4y ago

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.

bainsfather 4y ago

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.

amelius 4y ago
Isn't the Quanta article supposed to be the 'friendly' overview?
- DIARRHEA_xd 4y ago
  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".

amelius 4y ago

Linear electrical networks have no maximum current, though.

pfdietz 4y ago

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.) https://en.wikipedia.org/wiki/Greedoid https://en.wikipedia.org/wiki/Greedoid