Degree Constrained Network Flows

Adrian Vetta
Department of Mathematics and Statistics and
School of Computer Science
McGill University


Wednesday, February 21, 2007
4:30 - 5:30 PM
Terman Engineering Center, Room 453


Abstract:

In a single-sink multicommodity network flow problem on a graph G= (N,A) we wish to route a set of demands from a collection of source nodes to a sink node t. We are interested in flows whose support graphs are restricted to have outdegree at most d at each node - these are termed d-furcated flows.

Our goal here is to minimise the maximum congestion at any node. Specifically, we examine the "congestion gap" for the class of d- furcated flows; this is the maximum ratio between the congestion of an optimal d-furcated flow and an optimal fractional flow (i.e. a flow with no outdegree restriction).

For flows with outdegree at most d=1 (commonly known as confluent flows) the congestion gap is \Theta(log n) [CK+04]. For flows with outdegree at most d>1 the congestion gap is exactly 1+1/(d-1) [DS +06]. In particular, the congestion gap becomes bounded, namely 2, if the permissible outdegree increases from one to two.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html