A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria
Srinivasan, A. Chung-Piaw, T.
Srinivasan, A.
Citations
Altmetric:
Alternative Title
Abstract
We present the first constant-factor approximation algorithm for a fundamental problem: the store-and-forward packet routing problem on arbitrary networks. Furthermore, the queue sizes required at the edges are bounded by an absolute constant. Thus, this algorithm balances a global criterion (routing time) with a local criterion (maximum queue size) and shows how to get simultaneous good bounds for both. For this particular problem, approximating the routing time well, even without considering the queue sizes, was open. We then consider a class of such local vs. global problems in the context of covering integer programs and show how to improve the local criterion by a logarithmic factor by losing a constant factor in the global criterion. © 2001 Society for Industrial and Applied Mathematics.
Keywords
Approximation algorithms, Covering integer programs, Discrete ham-sandwich theorems, Linear programming, Multicommodity flow, Packet routing, Randomized algorithms, Randomized rounding, Rounding theorems
Source Title
SIAM Journal on Computing
Publisher
Series/Report No.
Collections
Rights
Date
2000
DOI
Type
Article