论文题目：Stability vs. Optimality in Sel sh Ring Routing

论文作者：Bo Chen, Xujin Chen, Jie Hu, Xiaodong Hu

论文摘要: We study asymmetric atomic selfish routing in ring networks, which has diverse practical applications in network design and analysis. We are concerned with minimizing the maximum latency of sourcedestination node-pairs over links with linear latencies. We obtain the first constant upper bound on the price of anarchy and significantly improve the existing upper bounds on the price of stability. Moreover, we show that there exists an optimal solution that is a good approximate Nash equilibrium. Finally, we present better performance analysis and fast implementation of pseudo-polynomial algorithms for computing approximate Nash equilibria.