Chen, Bo, Dr., Chen, Xujin and Hu, Xiaodong. (2010) The price of atomic selfish ring routing. Journal of Combinatorial Optimization, Vol.19 (No.3). pp. 258-278. ISSN 1382-6905

Full text not available from this repository.

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
Date:	April 2010
Volume:	Vol.19
Number:	No.3
Number of Pages:	21
Page Range:	pp. 258-278
Identification Number:	10.1007/s10878-008-9171-z
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
URI:	http://wrap.warwick.ac.uk/id/eprint/6231

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item