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


Gyula Pap
Weighted linear matroid parity - A primal-dual approach


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" [...]


  unsecured loans . What makes Viagra Strips better than other forms of this medicine is its easiness of usage.