Matching, Matroids, and Extensions

Perhaps the two most fundamental well-solved models in combinatorial optimization are the optimal matching problem and the optimal matroid intersection problem. We review the basic results for both, and describe some more recent advances. Then we discuss extensions of these models, in particular, two recent ones -- jump systems and path-matchings