I was going through the topic of matroid structures for the problems like Activity selection ,minimum spanning tree. I also came to know how to solve if a problem exhibits matroid structure. The statement says that problems that have matroid structure will have a greedy algorithm. But by just showing matroid structure for a problem does it mean greedy algorithm is the optimal algorithm for that problem?
Modified 2 years, 6 months ago
Viewed 44 times
$\begingroup$ The greedy algorithm solves the maximum weight basis problem in every matroid. If you problem is equivalent to the maximum weight basis problem in some matroid, then the corresponding greedy algorithm will solve it optimally. $\endgroup$– Yuval FilmusNov 22, 2020 at 8:01
$\begingroup$ See for example Wikipedia. $\endgroup$– Yuval FilmusNov 22, 2020 at 12:04
Add a comment |