23
$\begingroup$

Initially, matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy algorithms to find optimal solutions. The concept of greedoids was later introduced to generalize this structure to capture more problems that allow for optimal solutions to be found by greedy methods.

How often do these structures arise in algorithm design?

Furthermore, more often than not a greedy algorithm will not be able to fully capture what is necessary to find optimal solutions, but may still find very good approximate solutions (Bin Packing, for example). Given that, is there a way to measure how "close" a problem is to a greedoid or matroid?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
19
$\begingroup$

It's difficult to answer the question "how often". But as with all "underlying structures" the benefit comes from recognizing that the underlying problem one is trying to solve has a matroid (or greedoid) structure. It's not just matroid problems. The matroid intersection problem has a specific model (bipartite matching).

Nick Harvey did his Ph.D thesis fairly recently on algorithms for matroid problems and also looked at submodular function optimization (which generalizes matroid problems). Reading the introduction and background to the thesis might be helpful.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ I just want to add a note regarding "closeness". If a greedy algorithm gives a k-approximation, the problem may be structured as a k-matroid. $\endgroup$
    – Nicholas Mancuso
    Commented Apr 9, 2012 at 18:26
  • $\begingroup$ +1. Nice answer. I wonder why the thesis says a submodular function is a generalization or abstract of a matroid? The only connection I can find between the two are the rank of a submatroid on a subset is a submodular function. $\endgroup$
    – Tim
    Commented Jan 2, 2013 at 0:18
  • 2
    $\begingroup$ There's a very elegant geometric connection. To understand this better, you should check out en.wikipedia.org/wiki/Polymatroid. Roughly, if the polytope associated with a submodular function has specific properties, then you get a matroid. For more on this, see Satoru Fujishige's book: kurims.kyoto-u.ac.jp/~fujishig/Book1a.html $\endgroup$
    – Suresh
    Commented Jan 2, 2013 at 1:09
  • 5
    $\begingroup$ As indicated in CLRS (page 437 of the 3nd edition), the matroid theory does not cover the activity-selection problem and the Huffman coding problem. Does the greedoid theory cover them? $\endgroup$
    – hengxin
    Commented Dec 3, 2013 at 13:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.