Integer Multicommodity Flows with Reduced Demands

Srivastav, Anand and Stangier, Peter (1993) Integer Multicommodity Flows with Reduced Demands.
Published In: AlgorithmsESA '93 : First Annual European Symposium Bad Honnef, Germany September 30 - October 2, 1993 Proceedings, Lecture notes in computer science. 726 Springer 1993, pp. 360-371.

Abstract

Given a supply graph G=(V,E), a demand graph H=(T,D), edge capacities c:Emapsto Nset and requests r:Dmapsto Nset, we consider the problem of finding integer multiflows subject to c, r. Korach and Penn constructed approximate integer multiflows for planar graphs, but no results were known for the general case. Via derandomization we present a polynomial-time approximation algorithm. There are two cases: (a) The main result is: For fractional solvable instances (G,H,c,r) and each 0 < epsilon leqfrac{9}{10} our algorithm finds in polynomial-time an integer multiflow subject to c, such that for all d in D the d-th flow value satisfies f(d) ge (1-ep)r(d), provided that capacities and requests are not too small, i.e c,r = Omega (frac{1}{epsilon^2}log(|E|+|D|)). In particular, if c,r ge 36 lceil log 2(|E|+|D| +1) ceil we have a strongly polynomial-time algorithm and the first œ-factor approximation. (b) If the problem is not fractionally solvable we can reduce it to the case mentioned above decreasing the requests in an optimal way. This can be done by linear programming and the results of (a) apply. The design and analysis of the algorithm require new techniques for randomized rounding as well as for derandomization. One key tool is an algorithmic version of the classical Angluin-Valiant inequality (a variant of the well known Chernoff-Hoeffding bound) estimating the tail of weighted sums of Bernoulli trials, which was not previously known and might be of independent interest in computational probability theory. The significance of our rounding algorithm is emphasized by the fact that there is a rich combinatorial theory exhibiting many examples of fractionally solvable problems, but finding approximate integer solutions even for fractionally solvable problems is NP-hard as it is shown in this paper.


Actions:
Download: [img] Postscript - Preprinted Version
Download (226kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr93-146
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 11:33
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/146