Brief announcement: Stateless distributed algorithms for near optimal maximum multicommodity flows

Abstract

We design a stateless and distributed solution to the problem of maximum multicommodity flows-route the maximum amount of flow between given source-sink pairs, possibly split along several paths, subject to edge-capacity constraints. Our main contribution is in extending the work of [1, 2] to the case where the flow can be routed along possibly exponentially many different paths. Our algorithm, stalling from an arbitrary feasible flow, always maintains a feasible flow, and reaches a 1 + ∈ approximation of maximum benefit value in Õ(n2) rounds.