|
|
Combinatorial Algorithms for Flow Problems
Hladík, Richard ; Koutecký, Martin (advisor) ; Vegh, Laszlo (referee)
The multicommodity flow problem (MCF) and the length-bounded flow problem (LBF) are two generalisations of the maximum flow problem. Both can be solved us- ing linear programming and approximated using fully polynomial-time approximation schemes (FPTASs). However, there are no known algorithms for them that are at the same time 1) exact, 2) polynomial, and 3) combinatorial and/or not relying on general methods like linear programming. Multicommodity flow is sometimes called "the easiest problem with no combinatorial algorithm". In this thesis, we summarise problem-specific as well as general methods used to solve these problems. We propose two new combi- natorial algorithms, one based on the Frank-Wolfe method for convex optimisation (for MCF and LBF), and the other one based on most helpful cycle cancelling (for MCF), and prove that in networks with polynomial demands they both run in poly(input size, 1/ε) time. We also present some results from polyhedral theory, examining the circuits of MCF and LBF polyhedra. On the one hand, we prove that the existence of a circuit-like set consisting of vectors of small norm would make both algorithms nearly-exact (i.e., with ‰(log 1/ε) convergence). On the other hand, we prove that exponential circuits exist for both MCF and LBF. The existence of a circuit-like set...
|
guest ::
