A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria

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.