Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem

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 an O(log n)-approximation algorithm for congestion minimization [6]. We study the case of capacitated networks, where each node v has its own capacity [lowercase mu](v). Indeed, it was recently shown that demand maximization is inapproximable to within polynomial factors in capacitated networks [18]. We circumvent this lower bound in two ways. First, we prove that there is an O(log6 n)-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 factor O(log6 n)-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 approximation-algorithm for congestion minimization in a special class of capacitated networks that may be of independent interest. Specifically, we present an O(log4 n)-approximation algorithm for congestion minimization in monotonic networks - those networks with the property that [lowercase mu](u) less than or equal to [lowercase mu](v) for each arc (u, v).