The Library
The price of atomic selfish ring routing
Tools
Chen, Bo, Chen, Xujin and Hu, Xiaodong (2010) The price of atomic selfish ring routing. Journal of Combinatorial Optimization, Vol.19 (No.3). pp. 258-278. doi:10.1007/s10878-008-9171-z ISSN 1382-6905.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s10878-008-9171-z
Abstract
We study selfish routing in ring networks with respect to minimizing the maximum latency. Our main result is an establishment of constant bounds on the price of stability (PoS) for routing unsplittable flows with linear latency. We show that the PoS is at most 6.83, which reduces to 4.57 when the linear latency functions are homogeneous. We also show the existence of a (54,1)-approximate Nash equilibrium. Additionally we address some algorithmic issues for computing an approximate Nash equilibrium.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Divisions: | Faculty of Social Sciences > Warwick Business School | ||||
Journal or Publication Title: | Journal of Combinatorial Optimization | ||||
Publisher: | Springer New York LLC | ||||
ISSN: | 1382-6905 | ||||
Official Date: | April 2010 | ||||
Dates: |
|
||||
Volume: | Vol.19 | ||||
Number: | No.3 | ||||
Number of Pages: | 21 | ||||
Page Range: | pp. 258-278 | ||||
DOI: | 10.1007/s10878-008-9171-z | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |