Fast deterministic approximation for the multicommodity flow problem
Radzik, Tomasz

Data: 1997
Resum: In this paper we consider an optimization version of the multicommodity flow problem which is known as the maximum concurrent flow problem. We show that an approximate solution to this problem can be computed deterministically using O (k((Epsilon)^-2 + log k) log n) 1-commodity minimum-cost flow computations, where k is the number of commodities, n is the number of nodes, and (Epsilon) is the desired precision. We obtain this bound by proving that in the randomized algorithm developed by Leighton et al. (1995) the random selection of commodities can be replaced by the deterministic round-robin without increasing the total running time. Our bound significantly improves the previously known deterministic upper bounds and matches the best known randomized upper bound for the approximation concurrent flow problem. .
Drets: Tots els drets reservats.
Llengua: Anglès
Document: Article ; recerca ; Versió publicada
Matèria: Network flow ; Multicommodity flow ; Concurrent flow ; Approximate solution ; Network optimization
Publicat a: Mathematical Programming, vol. 78 n. 1 (1997) p. 43-58, ISSN 0025-5610

16 p, 827.8 KB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2023-06-03

   Favorit i Compartir