Abstract: Ein wunderbarer Satz von Gessel-Viennot verbindet nicht-kreuzende Wegesysteme mit Determinanten. Es soll gezeigt werden, wie erstens dieser Satz alle wesentlichen Determinanteneigenschaften in einem Bild impliziert ("proof by picture"), und zweitens an Hand von Beispielen, wie man damit einige (gar nicht leichte) kombinatorische Anzahlprobleme lösen kann.
Abstract: Although fractional multicommodity flow problems can be solved in polynomial time via linear programming solution techniques, the problems are often quite large and can be quite difficult to solve exactly in practice. In many situations, approximate solutions suffice. For this reason, a number of researchers have proposed polynomial time approximation schemes for these problems, which have proven in practice to find approximate solutions an order of magnitude faster than approximate solutions obtained by LP methods.
We present the first approximation scheme for maximum multicommodity flow that is independent of the number of commodities k, and our algorithm improves upon the runtime of previous algorithms by this factor of k. For maximum concurrent flow, and minimum cost concurrent flow, we present algorithms that are faster than the current known algorithms when the graph is sparse or the number of commodities k is large, i.e. k > m/n (where m is the number of arcs and n is the number of nodes in the graph). Our algorithms are simple, deterministic, and for the versions without costs, they are strongly polynomial.
We also discuss extensions of these ideas to generalized flows, and to covering linear programs with upper bounds on the variables (such as network design problems).