Meet and merge: Approximation algorithms for confluent flows

摘要

In this paper, we investigate the problem of determining confluent flows with minimum congestion. A flow of a given commodity 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.We consider the single-commodity confluent flow problem, in which we are given an n-node directed network G, a sink t 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 edge congestion. Our main result is an approximation algorithm, based on randomized rounding, for the special case when all the supplies are uniform; the algorithm finds a confluent flow with edge (and node) congestion O(C2log3n), where C is the node congestion of a splittable flow with minimum node congestion; here the node congestion of a flow is the maximum, over all nodes other than t, of the congestion at a node. This implies an O˜(n) approximation algorithm for the problem with uniform supplies. Our result relies on the analysis of a natural probabilistic process defined on directed acyclic graphs, that may be of independent interest.For tree networks, we present an optimal polynomial-time algorithm for a multi-sink generalization of the above confluent flow problem. We show that it is NP-hard to approximate the congestion of the optimal confluent flow for general networks to within a factor of 32. We also establish a lower bound on the gap between confluent and splittable flows, and consider multi-commodity and fractional versions of confluent flow problems.