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$ – Yuval Filmus Nov 22 '20 at 8:01
  • $\begingroup$ See for example Wikipedia. $\endgroup$ – Yuval Filmus Nov 22 '20 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.