Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/44984
Title: A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria
Authors: Srinivasan, A.
Chung-Piaw, T. 
Keywords: Approximation algorithms
Covering integer programs
Discrete ham-sandwich theorems
Linear programming
Multicommodity flow
Packet routing
Randomized algorithms
Randomized rounding
Rounding theorems
Issue Date: 2000
Source: 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.

Page view(s)

77
checked on Dec 8, 2017

Google ScholarTM

Check


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