94. Approximation of disjoint A-paths via fractional matroid matching
Invited abstract in session TC-3: Approximation algorithms for graph problems, stream Approximation algorithms.
Thursday, 12:00 - 13:30Room: C 104
Authors (first author is the speaker)
| 1. | Gyula Pap
|
| Dept. of Operations Research, Eötvös University |
Abstract
The disjoint A-path problem, mostly known for Mader’s min-max theorems, is related with matroid matching, approximation algorithms, and group theoretical models. We describe a reduction of the fractional disjoint A-path problem to the fractional matroid matching problem - a reduction that also implies an efficient algorithm as the matroid used has a linear representation. There is a 3/2 integrality gap for the matroid matching problem in linear matroids, and also for the disjoint A-paths problem. We explore the relationship between these two gaps, and how they imply approximation algorithms. We would also use this to describe the difficulty of some related open problems, including the problem of finding maximum number of disjoint even A-paths.
Keywords
- Complexity and efficiency of optimization algorithms
- Linear and nonlinear optimization
Status: accepted
Back to the list of papers