FOCS Conference 2015 Conference Paper
Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem
- F. Bruce Shepherd
- Adrian Vetta
- Gordon T. Wilfong
A single-sink confluent flow is a routing of multiple demands to a sink r such that any flow exiting a node v must use a single arc. Hence, a confluent flow routes on a tree within the network. In uncapacitated (or uniform-capacity) networks, there is an O(1)-approximation algorithm for demand maximization and a logarithmic approximation algorithm for congestion minimization [6]. We study the case of capacitated networks, where each node v has its own capacity μ(v). Indeed, it was recently shown that demand maximization is in approximable to within polynomial factors in capacitated networks [20]. We circumvent this lower bound in two ways. First, we prove that there is a polylogarithmic approximation algorithm for demand maximization in networks that satisfy the ubiquitous no-bottleneck assumption (NBA). Second, we show a bicriteria result for capacitated networks without the NBA: there is a polylog factor approximation guarantee for demand maximization provided we allow congestion 2. We model the capacitated confluent flows problem using a multilayer linear programming formulation. At the heart of our approach for demand maximization is a rounding procedure for flows on multilayer networks which can be viewed as a proposal algorithm for an extension of stable matchings. In addition, the demand maximization algorithms require, as a subroutine, an algorithm for approximate congestion minimization in a special class of capacitated networks that may be of independent interest. Specifically, we present a polylogarithmic approximation algorithm for congestion minimization in monotonic networks - those networks with the property that μ(u) ≤ μ(v) for each arc (u, v).