Title: A weighted linear matroid parity algorithm
| Speaker: | Satoru Iwata |
| Affiliation: | University of Tokyo |
| Location: | MC 5501 |
| Reception: | MC 5511 |
Abstract:
The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Nevertheless, Lovasz (1978) showed that this problem admits a min-max formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem.
In this talk, we present a combinatorial, deterministic, polynomial-time algorithm for the weighted linear matroid parity problem. The algorithm builds on a polynomial matrix formulation using Pfaffian and adopts a primal-dual approach based on the augmenting path algorithm of Gabow and Stallmann (1986) for the unweighted problem.
This is a joint work with Yusuke Kobayashi.