Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks

DOI10.1145/195058.195238zbMath1344.68278OpenAlexW2094619585MaRDI QIDQ2817640

Leighton, Tom, Baruch Awerbuch

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Network design and communication in computer systems (68M10) Distributed systems (68M14) Approximation algorithms (68W25)

Related Items (7)

Improved bounds on the max-flow min-cut ratio for multicommodity flows ⋮ Authenticated adversarial routing ⋮ On the stability of dynamic diffusion load balancing ⋮ Adaptive packet routing for bursty adversarial traffic ⋮ Unnamed Item ⋮ Near-Optimal Distributed Maximum Flow ⋮ Distributed agreement in dynamic peer-to-peer networks

This page was built for publication: Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks