1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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, 2020 at 8:01
  • $\begingroup$ See for example Wikipedia. $\endgroup$
    – Yuval Filmus
    Nov 22, 2020 at 12:04

0

Reset to default

Your Answer

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