TY - CHAP

T1 - Multicommodity demand flow in a tree (extended abstract)

AU - Chekuri, Chandra

AU - Mydlarz, Marcelo

AU - Shepherd, F. Bruce

PY - 2003

Y1 - 2003

N2 - We consider requests for capacity in a given tree network T = (V, E) where each edge of the tree has some integer capacity ue. Each request consists of 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 provide 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, Vazirani, and Yannakakis [5] 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. In this paper we establish for the first time that the natural linear programming relaxation has a constant factor gap, a factor of 4, for the case of arbitrary profits. We then discuss the situation for 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 showing that the integrality gap for demand version of such a problem is at most 12 times that for the unit demand case. We use techniques of Kolliopoulos and Stein [8,9] to obtain this. We also obtain, via this method, improved algorithms for the 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 of the tree has some integer capacity ue. Each request consists of 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 provide 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, Vazirani, and Yannakakis [5] 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. In this paper we establish for the first time that the natural linear programming relaxation has a constant factor gap, a factor of 4, for the case of arbitrary profits. We then discuss the situation for 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 showing that the integrality gap for demand version of such a problem is at most 12 times that for the unit demand case. We use techniques of Kolliopoulos and Stein [8,9] to obtain this. We also obtain, via this method, improved algorithms for the 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=35248848767&partnerID=8YFLogxK

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

U2 - 10.1007/3-540-45061-0_34

DO - 10.1007/3-540-45061-0_34

M3 - Chapter

AN - SCOPUS:35248848767

SN - 3540404937

SN - 9783540404934

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 410

EP - 425

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Baeten, Jos C. M.

A2 - Lenstra, Jan Karel

A2 - Parrow, Joachim

A2 - Woeginger, Gerhard J.

PB - Springer

ER -