In Cormen's "Introduction to algorithms" it is stated that matroid theory cannot be applied to justify the greedy algorithm given for the construction of Huffman's codes. I was wondering whether this can be proved formally. Is there something inherent in the problem that makes it orthogonal to matroids?

  • 4
    $\begingroup$ Greedy algorithms don't have a formal definition and there is no consensus even amongst algorithms researchers on whether some algorithms should be considered greedy. A particularly simple type of greedy algorithm works for a specific problem in matroids, namely the maximum weight independent set. There is no reason to look for matroids everywhere a greedy-type algorithm works. $\endgroup$ Commented Jun 10 at 16:47


Your Answer

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

Browse other questions tagged or ask your own question.