Flow-Based Problem Solving in Combinatorial Optimization

Abstract

Ever since the seminal work of Ford and Fulkerson [33] network flows belong to the most important and fundamental class of problems in combinatorial optimiza-tion. Network flow problems arise in real-world applications and in theoretical optimization problems that, at first sight, might not seem to involve networks at all. In this thesis, we consider three different problems that all have very strong connections to network flows and flow decomposition.

The first part of this thesis considers the single source unsplittable flow problem,introduced by Kleinberg 43 in 1996. In a digraph with one source and several destination nodes with associated demands, an unsplittable flow routes each de-mand along a single path from the common source to its destination. Given some fractional flow xthat satisfies all demands, it is a natural question to ask for an unsplittable flow y that does not deviate from xby too much, i.e., Ya xafor all arcs a. Twenty-five years ago, Dinitz, Garg, and Goemans [25] proved that there is an unsplittable flow ysuch that y_ax_a+ d_maxfor all arcs a, where d_maxdenotes the maximum demand value. Our first contribution is a considerably simpler one-page proof for this classical result. Secondly, we show that there is an unsplitt able flow ysuch that ya X_a-d_maxfor all arcs a. Finally, we prove existence of an unsplittable flow that simultaneously satisfies the upper and lower bounds for the special case where demands are integer multiples of each other. For arbitrary de-mand values, we prove the weaker simultaneous bounds-dmax for all arcs a.

Finding optimal subgraphs of a surface-embedded graph that satisfy certain topological properties is a basic subject in topological graph theory and an impor-tant ingredient in many algorithms. In the second part of this thesis, we study a variant of the minimum-cost circulation problemwith such an additional topo-logical constraint. Given a directed graph Dcellularly embedded in a surface together with nonnegative cost con its arcs and any integer circulation yin D,find a minimum-cost nonnegative integer circulation in D that is Z-homologous to y. Here, a circulation xsaid to be Z-homologous to yif their difference x-yis a linear combination of facial circulations with integer coefficients, where a facial circulationis a circulation that sends one unit along the boundary of a single face.

The above-mentioned problem is NP-hard for general non-orientable surfaces. We present a polynomial-time algorithm for non-orientable surfaces of fixed genus. For this purpose, we provide a characterization of Z-homology by exploiting a flow decomposition technique. This allows us to reformulate the problem as an integer program in standard form with a constant number of quality constraints, provided that the genus is fixed. This integer program can then be efficiently solved using some general integer programming techniques.

In the third part of this thesis, we consider the problem of allocating indi-visible resources to players so as to maximize the minimum total value that any player receives. This problem is sometimes dubbed the Santa Claus problem,and its different variants have been subject to extensive research toward approxima-tion algorithms over the past two decades.