Meet and Merge: Approximation Algorithms for Confluent Flows

Rajmohan Rajaraman
Northeastern University

A flow of a given commodity in a network is said to be confluent if at
any node all the flow of the commodity departs along a single edge.
Confluent flows appear in a variety of application areas ranging from
wireless communications to evacuations; in fact, most flows in the
Internet are confluent since Internet routing is destination based.

In this talk, we consider the problem of determining confluent flows
with minimum congestion.  We will focus on the single commodity
confluent flow problem, in which we are given an n-node directed
network, a sink, and supplies at each node, and the goal is to find a
confluent flow that routes all the supplies to the sink while
minimizing the maximum flow on any edge.  Our main result is a simple
O(n^{1/2} polylog(n))-approximation algorithm, based on randomized
rounding, for the special case when all the supplies are uniform.  Our
result relies on the analysis of a natural probabilistic process
defined on directed acyclic graphs, that may be of independent
interest.

We will also discuss the relationship between confluent and (standard)
splittable flows, the hardness of approximability of the problem, and
an optimal solution for a variant of the problem on tree networks.  If
time permits, we will consider the multicommodity and fractional
versions of confluent flow problems.

(Joint work with Jiangzhuo Chen and Ravi Sundaram.)