Optimization Online


Faster Approximation Schemes for Fractional Multicommodity Flow Problems

George Karakostas (gk***at***cas.mcmaster.ca)

Abstract: We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of minimal dependency on the number of commodities k. We show that by modifying the algorithms by Garg & Konemann and Fleischer we can reduce their running time to a logarithmic dependence on k, and essentially match the running time of Fleischer's FPTAS for the maximum multicommodity flow problem if we want only an implicit representation of the solution flow. In case we want to calculate explicitly the solution flow, our schemes run in time poly-logarithmic in nk (n is the number of nodes in the network). This is within a poly-logarithmic factor of the trivial lower bound of \Omega(nk).

Keywords: fractional multicommodity flow approximation schemes

Category 1: Network Optimization

Citation: Dept. of Computing & Software, McMaster University, Rm. ITB/218 1280 Main St. W. Hamilton, ON L8S 4K1 CANADA June 2003

Download: [Postscript][PDF]

Entry Submitted: 06/26/2003
Entry Accepted: 06/30/2003
Entry Last Modified: 05/03/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society