About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
PODC 2008
Conference paper
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.