Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/53281
Title: Constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria
Authors: Srinivasan, Aravind 
Teo, Chung-Piaw 
Issue Date: 1997
Source: Srinivasan, Aravind,Teo, Chung-Piaw (1997). Constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria. Conference Proceedings of the Annual ACM Symposium on Theory of Computing : 636-643. ScholarBank@NUS Repository.
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 (though, 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 more than a constant (roughly logarithmic) factor, by losing a constant factor in the global criterion; this is in comparison with the current-best algorithms.
Source Title: Conference Proceedings of the Annual ACM Symposium on Theory of Computing
URI: http://scholarbank.nus.edu.sg/handle/10635/53281
ISSN: 07349025
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

97
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.