**Tuesday, 16:15 - 16:40 h, Room: H 3005**

**Gyula Pap**

Weighted linear matroid parity - A primal-dual approach

**Abstract:**

In the matroid parity problem we are given a matroid partitioned into pairs - subsets of cardinality 2. A set of pairs is called a matching if their union is an independent set. The (unweighted) matroid parity problem is to maximize the cardinality of a matching. This problem is solvable in polynomial time for linear matroids by LovĂˇsz' famous result - a generalization of graphical matching, and (linear) matroid intersection, both of which are solvable also in the weighted version. Thus one suspects the natural weighted version of linear matroid matching to also be tractable: consider a linear matroid whose elements are assigned weights, and partitioned into pairs - find a matching whose total weight is maximal. A solution to this problem would generalize both of Edmonds' algorithms, for matching, and for (linear) matroid intersection as well. In this talk a primal-dual algorithm is presented to solve weighted linear matroid matching in strongly polynomial time. A different solution to this problem has been found independently by Iwata.

Talk 3 of the invited session Tue.3.H 3005

**"Matroid parity"** [...]

Cluster 2

**"Combinatorial optimization"** [...]