Faster Approximation Schemes for Fractional Multicommodity Flow Problems via Dynamic Graph Algorithms

Details Faster Approximation Schemes for Fractional Multicommodity Flow Problems via Dynamic Graph Algorithms Faster Approximation Schemes for Fractional Multicommodity Flow Problems via Dynamic Graph Algorithms

2010-03-30

arxiv.org/abs/1003.5907v2

Computer Science

Data Structures and Algorithms

Scientific paper

We combine the work of Garg and Konemann, and Fleischer with ideas from dynamic graph algorithms to obtain faster (1-eps)-approximation schemes for various versions of the multicommodity flow problem. In particular, if eps is moderately small and the size of every number used in the input instance is polynomially bounded, the running times of our algorithms match - up to poly-logarithmic factors and some provably optimal terms - the Omega(mn) flow-decomposition barrier for single-commodity flow.

Affiliated with

Also associated with

No associations

Rating

Faster Approximation Schemes for Fractional Multicommodity Flow Problems via Dynamic Graph Algorithms 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 Faster Approximation Schemes for Fractional Multicommodity Flow Problems via Dynamic Graph Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Approximation Schemes for Fractional Multicommodity Flow Problems via Dynamic Graph Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-81794