Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

DOI10.1145/1806689.1806708MaRDI QIDQ2875138zbMATH OpenOpenAlexFDO

Authors Aleksander Mądry

Publication date 13 August 2014

Published in Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.5907

zbMATH Keywords

dynamic graph algorithmsmulticommodity flow problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21)

Abstract: 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.

Recommendations

• Faster approximation schemes for fractional multicommodity flow problems
• Approximating fractional multicommodity flow independent of the number of commodities
• Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
• Faster approximation schemes for fractional multicommodity flow problems
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems

Cited in

(17)

• Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks
• Deterministic incremental APSP with polylogarithmic update time and stretch
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Approximation schemes for fractional multicommodity flow problems
• Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence
• Approximating fractional multicommodity flow independent of the number of commodities
• Dynamic single-source shortest paths in Erdős-Rényi random graphs
• Distributed distance computation and routing with small messages
• Near-linear time approximation schemes for some implicit fractional packing problems
• Incremental single-source shortest paths in digraphs with arbitrary positive arc weights
• Hardness results for structured linear systems
• Faster approximation schemes for fractional multicommodity flow problems
• Faster approximation schemes for fractional multicommodity flow problems
• Single-source shortest paths in the CONGEST model with improved bounds

This page was built for publication: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875138)