Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm in the process of learning about Matroid Theory (I'm reading Oxley's book). I came to this from combinatorics and topology.

Now, I just read of connections between matroids and combinatorial optimization. Yet the only example I've seen so far is that of the greedy algorithm.

So, I'm wondering if there is some astounding application of matroids to optimization. By that I mean either something that can be solved with matroids and for which no matroids-free solution is known, or something that can be solved much more easily using matroids.

share|cite|improve this question

It's not the solution that employs matroids but the problems. The idea is that many natural problems exhibit some matroidal structure, a common structure which algorithms can exploit. In other words, many problems that one wants to solve in practice are not arbitrary but have some "simplifying assumptions". In many cases, these assumptions imply that something is a matroid. The goal is to develop a small number of algorithms for a wide range of problems. Therefore we want to abstract and find what "simplifying assumptions" are common in practice and useful from an algorithmic point of view. Being a matroid is one of them.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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