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?

  • $\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$ Commented Nov 22, 2020 at 8:01
  • $\begingroup$ See for example Wikipedia. $\endgroup$ Commented Nov 22, 2020 at 12:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.