Intricately connected to greedy algorithms are so called matroids, that are independence systems, satisfying extra conditions. One of the many different equivalent definitions is that an independence system is a matroid if and only if the greedy algorithm produces a basis of it with optimal weight for every weight function.
Do you know of any way to measure the failure of a local solution from being optimal in the global context? I keep running into this kind of problem where there exists obstruction between the local and global context…
This is a really great question! I do not know the answer, and I feel like this is really hard as such a measure probably needs to vary drastically from setting to setting. I would be happy to be proven wrong! Completely speculative, but it is kind of weird that greed (I talk about the human trait) survived evolution pretty well. Its weird in the sense that greedy algorithm almost never produce the best results. But it seems like they produce “reasonably good” results in practice. And since math is mimicking the real world (or vice versa - I can’t tell), maybe a good first approximation to your question would be to analyze how well greedy algorithm do for “hard” graph theory problems compared the optimal solution. This should be known to Dr google. For example, “heuristic algorithms traveling salesman problem” gives a good bunch of hits that I haven’t check in more details. I hope that helps!
![Seungmin "그렇게, 천천히, 우리(As we are)" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/kAzmhLHePqU/mqdefault.jpg)
Intricately connected to greedy algorithms are so called matroids, that are independence systems, satisfying extra conditions. One of the many different equivalent definitions is that an independence system is a matroid if and only if the greedy algorithm produces a basis of it with optimal weight for every weight function.
That is right: thank you for the reminder! The spanning tree algorithm are examples. Could have mentioned that...
Do you know of any way to measure the failure of a local solution from being optimal in the global context? I keep running into this kind of problem where there exists obstruction between the local and global context…
This is a really great question!
I do not know the answer, and I feel like this is really hard as such a measure probably needs to vary drastically from setting to setting. I would be happy to be proven wrong!
Completely speculative, but it is kind of weird that greed (I talk about the human trait) survived evolution pretty well. Its weird in the sense that greedy algorithm almost never produce the best results. But it seems like they produce “reasonably good” results in practice.
And since math is mimicking the real world (or vice versa - I can’t tell), maybe a good first approximation to your question would be to analyze how well greedy algorithm do for “hard” graph theory problems compared the optimal solution. This should be known to Dr google. For example,
“heuristic algorithms traveling salesman problem” gives a good bunch of hits that I haven’t check in more details.
I hope that helps!
Always enjoy your vids 😁
I appreciate that! But maybe you are a bit too greedy ;-) "always" is a very huge word ;-)
@@VisualMath 🤣👏