Multicommodity demand flow in a tree and packing integer programs
- 1 August 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 3 (3), 27
- https://doi.org/10.1145/1273340.1273343
Abstract
We consider requests for capacity in a given tree network T = ( V , E ) where each edge e of the tree has some integer capacity u e . Each request f is a node pair with an integer demand d f and a profit w f 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 d max is at most the minimum edge capacity u min , 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.Keywords
This publication has 14 references indexed in Scilit:
- A quasi-PTAS for unsplittable flow on line graphsPublished by Association for Computing Machinery (ACM) ,2006
- Hardness of the undirected edge-disjoint paths problemPublished by Association for Computing Machinery (ACM) ,2005
- Approximating disjoint-path problems using packing integer programsMathematical Programming, 2004
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problemsJournal of Computer and System Sciences, 2003
- The Demand Matching ProblemLecture Notes in Computer Science, 2002
- A unified approach to approximating resource allocation and schedulingJournal of the ACM, 2001
- A cycle augmentation algorithm for minimum cost multicommodity flows on a ringDiscrete Applied Mathematics, 2001
- Approximation Algorithms for Single-Source Unsplittable FlowSIAM Journal on Computing, 2001
- On the Single-Source Unsplittable Flow ProblemCombinatorica, 1999
- Primal-dual approximation algorithms for integral flow and multicut in treesAlgorithmica, 1997