4
$\begingroup$

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.

1 Answers 1

2

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.