Please use this identifier to cite or link to this item:
|Title:||Constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria||Authors:||Srinivasan, Aravind
|Issue Date:||1997||Citation:||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.
checked on Aug 18, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.