Multicommodity demand flow in a tree and packing integer programs

Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd

Research output: Contribution to journalArticlepeer-review

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 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.

Original languageEnglish (US)
Article number1273343
JournalACM Transactions on Algorithms
Volume3
Issue number3
DOIs
StatePublished - Aug 1 2007

Keywords

  • Approximation algorithm
  • Integer multicommodity flow
  • Integrality gap
  • Packing integer program
  • Tree

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint Dive into the research topics of 'Multicommodity demand flow in a tree and packing integer programs'. Together they form a unique fingerprint.

Cite this