Invited Session Tue.3.H 3005

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

Cluster 2: Combinatorial optimization [...]

Matroid parity


Chair: Tamás Király



Tuesday, 15:15 - 15:40 h, Room: H 3005, Talk 1

Ho Yee Cheung
Algebraic algorithms for linear matroid parity problems

Coauthors: Lap Chi Lau, Kai Man Leung


We present faster and simpler algebraic algorithms for the linear matroid parity
problem and its applications. For the linear matroid parity problem, we obtain
a simple randomized algorithm with running time O(mrω-1), which
improves the O(mrω)-time algorithm by Gabow and Stallmann. We also
present a very simple alternative algorithm with running time O(mr2).
We further improve the algebraic algorithms for some specific graph problems
of interest.
We present faster randomized algorithms for the Mader's disjoint S-path
problem and the graphic matroid parity problem.
The techniques are based on the algebraic algorithmic framework developed by
Mucha, Sankowski and Harvey.
While linear matroid parity and Mader's disjoint S-path
are challenging generalizations for the design of combinatorial algorithms,
our results show that both the algebraic algorithms for linear
matroid intersection and graph matching can be extended nicely to
more general settings.
All algorithms are still faster than the existing algorithms even if fast matrix
multiplications are not used.
These provide simple algorithms that can be easily implemented.



Tuesday, 15:45 - 16:10 h, Room: H 3005, Talk 2

Satoru Iwata
Weighted linear matroid parity


The matroid parity problem was introduced as a common generalization of matching and matroid intersection problems.
In the worst case, it requires an exponential number of independence oracle calls.
Nevertheless, the problem is solvable if the matroid in question is represented by a matrix.
This is a result of Lovász (1980), who discovered a min-max theorem as well as a polynomial time algorithm.
Subsequently, more efficient algorithms have been developed for this linear matroid parity problem.
This talk presents a combinatorial, deterministic, strongly polynomial algorithm for its weighted version. The algorithm builds on a polynomial matrix formulation of the problem using Pfaffian and an augmenting path algorithm for the unweighted version by Gabow and Stallmann (1986).
Independently of this work, Gyula Pap has obtained the same result based on a different approach.



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

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.


  There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.