This course introduces discrete structures that help design of efficient algorithms for optimization. More specifically, it focuses on matching, matroids and extensions. The ultimate goal of this course is to explain the weighted linear matroid parity algorithm developed by S. Iwata and Y. Kobayashi (2017).
B. Korte and J. Vygen: Combinatorial Optimization, 5th ed., Springer-Verlag, 2010.
L. Lovasz and M. D. Plummer: Matching Theory, AMS, 2009.
A. Schrijver: Combinatorial Optimization --- Polyhedra and Efficiency, Springer-Verlag, 2003.
履修上の注意
Questions and discussions during the lecture will be welcome.