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

 

Satoru Iwata
Weighted linear matroid parity

 

Abstract:
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.

 

Talk 2 of the invited session Tue.3.H 3005
"Matroid parity" [...]
Cluster 2
"Combinatorial optimization" [...]

 

  unsecured loans . In this section we give only a brief summary recommendation for admission of Levitra Sale. Full information can be found in the instructions for receiving medications with vardenafil.