Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
From MaRDI portal
Publication:2875138
DOI10.1145/1806689.1806708zbMATH Open1293.05150arXiv1003.5907OpenAlexW2039303552MaRDI QIDQ2875138FDOQ2875138
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)
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.
Full work available at URL: https://arxiv.org/abs/1003.5907
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
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Distributed distance computation and routing with small messages
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
- Approximation schemes for fractional multicommodity flow problems
- Near-linear time approximation schemes for some implicit fractional packing problems
- Hardness Results for Structured Linear Systems
- Single-source shortest paths in the CONGEST model with improved bounds
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Approximating fractional multicommodity flow independent of the number of commodities
- Deterministic incremental APSP with polylogarithmic update time and stretch
- Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence
- Faster approximation schemes for fractional multicommodity flow problems
- A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
- Dynamic single-source shortest paths in Erdős-Rényi random graphs
- Incremental single-source shortest paths in digraphs with arbitrary positive arc weights
- Faster approximation schemes for fractional multicommodity flow problems
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)
