Matroid Parity

ABSTRACT:
This talk provides an overview on matroid parity, which was introduced in the 70s as a common generalization of matching and matroid intersection. In particular, it presents a recently developed polynomial-time algorithm for the weighted linear matroid parity problem and reports some computational results.

BIOGRAPHY:
Satoru Iwata obtained his Dr.Sc. degree from Kyoto University in 1996. He is currently a Professor at Department of Mathematical Informatics at the University of Tokyo. His research interests include combinatorial optimization, matroid theory, and their applications. He shared the Delbert Ray Fulkerson Prize in 2003 for his joint work on submodular function minimization.