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.


  In particular, Payday Loans Texas can cater to the needs of its residents. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.