|
|
Discrete Mathematics and Optimization Seminar
|
Oct. 19th, 2009
|
Algorithms for integral and half-integral multiflows
Gyula Pap
Cornell University
|
A classical problem in combinatorial optimization is that of maximum multiflows. We are given an undirected graph G=(V,E), and a set of terminals A subset of V. A multiflow is defined as a set of |A|(|A|-1)/2 flows between all pairs of distinct terminals. The goal is to maximize the total size of the multiflow, that is the sum of the size of all the |A|(|A|-1)/2 flows, subject to certain capacity constraints. Variations of the problem arise from edge- or node-capacities, and/or adding a (half-)integrality constraint. The problem is really interesting even for the special case of all-one node capacities, which is characterized by Mader's min-max formula, and solved by Lovász' linear matroid matching algorithm. Mader's formula also applies for arbitrary capacities, but matroid matching, in the obvious way of expanding the graph, only implies an exponential time algorithm.
The main result presented in this talk is a strongly polynomial time algorithm to find a maximum integral multiflow subject to node-capacities (the most general of all these variations). This improves on a result of Ibaraki, Karzanov and Nagamochi for the edge-capacitated, half-integral version, and on Keijsper, Pendavingh and Stougie's weakly polynomial time algorithm for the edge-capacitated, integral version. These results are generalized to the node-capacitated version, although using completely different tehniques. The half-integral node-capacitated multiflow problem is solved based on a recent result saying that the polytope of shortest maximum multiflows is half-integral, which implies a strongly polynomial algorithm via ellipsoid method and Frank and Tardos' diophantine approximation. To solve the integral node-capacitated multiflow problem, we first solve it to half-integrality, and then use a scaling-type argument motivated by Gerards' proximity lemma for b-matching to reduce the problem to small capacities. In the presentation we will also take a look at related results and techniques, such as a splitting-off algorithm for Lov\'asz' and Cherkassky's result, a divide-and-conquer-type argument for the edge-capacitated version.
|
|
|
|