Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks
DOI10.1145/195058.195238zbMATH Open1344.68278OpenAlexW2094619585MaRDI QIDQ2817640FDOQ2817640
Authors: Baruch Awerbuch, Tom Leighton 
Publication date: 1 September 2016
Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/195058.195238
Recommendations
- Fast approximation algorithms for multicommodity flow problems
- Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
- Greedy distributed optimization of multi-commodity flows
- Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
- Greedy distributed optimization of multi-commodity flows
Programming involving graphs or networks (90C35) Approximation algorithms (68W25) Network design and communication in computer systems (68M10) Distributed systems (68M14)
Cited In (9)
- Distributed agreement in dynamic peer-to-peer networks
- Near-optimal distributed maximum flow
- On the stability of dynamic diffusion load balancing
- Authenticated adversarial routing
- Towards robust and efficient computation in dynamic peer-to-peer networks
- Improved bounds on the max-flow min-cut ratio for multicommodity flows
- Adaptive packet routing for bursty adversarial traffic
- An efficient approach to optimization of semi‐stable routing in multicommodity flow networks
- A (k + 1)-Approximation Robust Network Flow Algorithm and a Tighter Heuristic Method Using Iterative Multiroute Flow
This page was built for publication: Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817640)
