Computer Science – Data Structures and Algorithms
Scientific paper
2012-02-15
Computer Science
Data Structures and Algorithms
Scientific paper
The maximum multicommodity flow problem is a natural generalization of the maximum flow problem to route multiple distinct flows. Obtaining a $1-\epsilon$ approximation to the multicommodity flow problem on graphs is a well-studied problem. In this paper we present an adaptation of recent advances in single-commodity flow algorithms to this problem. As the underlying linear systems in the electrical problems of multicommodity flow problems are no longer Laplacians, our approach is tailored to generate specialized systems which can be preconditioned and solved efficiently using Laplacians. Given an undirected graph with m edges and k commodities, we give algorithms that find $1-\epsilon$ approximate solutions to the maximum concurrent flow problem in time $\tilde{O}(m^{4/3}\poly(k,\epsilon^{-1}))$.
Kelner Jonathan A.
Miller Gerald
Peng Richard
No associations
LandOfFree
Beyond Laplacians: Faster Approximations of Multicommodity Flow in Undirected Graphs Using Quadratically Coupled Electrical Flows does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Beyond Laplacians: Faster Approximations of Multicommodity Flow in Undirected Graphs Using Quadratically Coupled Electrical Flows, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Beyond Laplacians: Faster Approximations of Multicommodity Flow in Undirected Graphs Using Quadratically Coupled Electrical Flows will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-558144