The price of atomic selfish ring routing |
| |
Authors: | Bo Chen Xujin Chen Xiaodong Hu |
| |
Institution: | 1.Warwick Business School (WBS) and Centre for Discrete Mathematics and its Applications (DIMAP),University of Warwick,Coventry,UK;2.Institute of Applied Mathematics,Chinese Academy of Sciences,Beijing,China |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|