TY - JOUR

T1 - Multicommodity demand flow in a tree and packing integer programs

AU - Chekuri, Chandra

AU - Mydlarz, Marcelo

AU - Shepherd, F. Bruce

PY - 2007/8/1

Y1 - 2007/8/1

N2 - We consider requests for capacity in a given tree network T = (V, E) where each edge e of the tree has some integer capacity ue. Each request f is a node pair with an integer demand df and a profit wf which is obtained if the request is satisfied. The objective is to find a set of demands that can be feasibly routed in the tree and which provides a maximum profit. This generalizes well-known problems, including the knapsack and b-matching problems. When all demands are 1, we have the integer multicommodity flow problem. Garg et al. [1997] had shown that this problem is NP-hard and gave a 2-approximation algorithm for the cardinality case (all profits are 1) via a primal-dual algorithm. Our main result establishes that the integrality gap of the natural linear programming relaxation is at most 4 for the case of arbitrary profits. Our proof is based on coloring paths on trees and this has other applications for wavelength assignment in optical network routing. We then consider the problem with arbitrary demands. When the maximum demand dmax is at most the minimum edge capacity umin, we show that the integrality gap of the LP is at most 48. This result is obtained by showing that the integrality gap for the demand version of such a problem is at most 11.542 times that for the unit-demand case. We use techniques of Kolliopoulos and Stein [2004, 2001] to obtain this. We also obtain, via this method, improved algorithms for line and ring networks. Applications and connections to other combinatorial problems are discussed.

AB - We consider requests for capacity in a given tree network T = (V, E) where each edge e of the tree has some integer capacity ue. Each request f is a node pair with an integer demand df and a profit wf which is obtained if the request is satisfied. The objective is to find a set of demands that can be feasibly routed in the tree and which provides a maximum profit. This generalizes well-known problems, including the knapsack and b-matching problems. When all demands are 1, we have the integer multicommodity flow problem. Garg et al. [1997] had shown that this problem is NP-hard and gave a 2-approximation algorithm for the cardinality case (all profits are 1) via a primal-dual algorithm. Our main result establishes that the integrality gap of the natural linear programming relaxation is at most 4 for the case of arbitrary profits. Our proof is based on coloring paths on trees and this has other applications for wavelength assignment in optical network routing. We then consider the problem with arbitrary demands. When the maximum demand dmax is at most the minimum edge capacity umin, we show that the integrality gap of the LP is at most 48. This result is obtained by showing that the integrality gap for the demand version of such a problem is at most 11.542 times that for the unit-demand case. We use techniques of Kolliopoulos and Stein [2004, 2001] to obtain this. We also obtain, via this method, improved algorithms for line and ring networks. Applications and connections to other combinatorial problems are discussed.

KW - Approximation algorithm

KW - Integer multicommodity flow

KW - Integrality gap

KW - Packing integer program

KW - Tree

UR - http://www.scopus.com/inward/record.url?scp=34548230391&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34548230391&partnerID=8YFLogxK

U2 - 10.1145/1273340.1273343

DO - 10.1145/1273340.1273343

M3 - Article

AN - SCOPUS:34548230391

VL - 3

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 3

M1 - 1273343

ER -