Please use this identifier to cite or link to this item:
|Title:||A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria||Authors:||Srinivasan, A.
Covering integer programs
Discrete ham-sandwich theorems
|Issue Date:||2000||Citation:||Srinivasan, A.,Chung-Piaw, T. (2000). A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria. SIAM Journal on Computing 30 (6) : 2051-2068. 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. 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.||Source Title:||SIAM Journal on Computing||URI:||http://scholarbank.nus.edu.sg/handle/10635/44984||ISSN:||00975397|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Aug 19, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.