Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/53281
DC Field | Value | |
---|---|---|
dc.title | Constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria | |
dc.contributor.author | Srinivasan, Aravind | |
dc.contributor.author | Teo, Chung-Piaw | |
dc.date.accessioned | 2014-05-19T02:56:35Z | |
dc.date.available | 2014-05-19T02:56:35Z | |
dc.date.issued | 1997 | |
dc.identifier.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. | |
dc.identifier.issn | 07349025 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/53281 | |
dc.description.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. | |
dc.source | Scopus | |
dc.type | Conference Paper | |
dc.contributor.department | DECISION SCIENCES | |
dc.contributor.department | INFORMATION SYSTEMS & COMPUTER SCIENCE | |
dc.description.sourcetitle | Conference Proceedings of the Annual ACM Symposium on Theory of Computing | |
dc.description.page | 636-643 | |
dc.description.coden | CATCD | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.