Premium
Flows on few paths: Algorithms and lower bounds
Author(s) -
Martens Maren,
Skutella Martin
Publication year - 2006
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20121
Subject(s) - mathematics , flow (mathematics) , path (computing) , upper and lower bounds , flow network , rounding , bounded function , generalization , multi commodity flow problem , approximation algorithm , combinatorics , algorithm , discrete mathematics , computer science , mathematical analysis , geometry , programming language , operating system
The classical network flow theory allows decomposition of flow into several chunks of arbitrary sizes traveling through the network on different paths. In the first part of this article we consider the unsplittable flow problem where all flow traveling from a source to a destination must be sent on only one path. We prove a lower bound of Ω (log m /log log m ) on the performance of a general class of algorithms for minimizing congestion where m is the number of edges in a graph. These algorithms start with a solution for the classical multicommodity flow problem, compute a path decomposition, and select one of its paths for each commodity in order to obtain an unsplittable flow. Our result matches the best known upper bound for randomized rounding—an algorithm of this type introduced by Raghavan and Thompson. The k‐splittable flow problem is a generalization of the unsplittable flow problem where the number of paths is bounded for each commodity. We study a new variant of this problem with additional constraints on the amount of flow being sent along each path. We present approximation results for two versions of this problem with the objective to minimize the congestion of the network. The key idea is to reduce the problem under consideration to an unsplittable flow problem while only losing a constant factor in the performance ratio. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(2), 68–76 2006