Matroids are powerful combinatorial structures that allow to model many combinatorial optimization problems exactly. Using them to design and analyze approximation algorithms for hard combinatorial optimization problems appears very promising but also very challenging.

In this talk, after describing some of the important features of matroids for optimization purposes, I will discuss some of its applications to the design and analysis of approximation algorithms.