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

DOI10.1145/195058.195238MaRDI QIDQ2817640zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(9)

• A (k + 1)-Approximation Robust Network Flow Algorithm and a Tighter Heuristic Method Using Iterative Multiroute Flow
• 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

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)