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.