Price of Anarchy, Locality Gap, and a Network Service Provider Game
作者： Nikhil Devanur , Naveen Garg , Rohit Khandekar , Vinayaka Pandit , Amin Saberi
DOI: 10.1007/11600930_105
关键词:
摘要: In this paper, we define a network service provider game. We show that the price of anarchy defined game can be bounded by analyzing local search heuristic for related facility location problem called k-facility problem. As result, has locality gap 5. This result is interest on its own. Our gives evidence to belief certain games are analysis heuristics.
springer.com
core.ac.uk
springerlink.com
acm.org 参考文章(10)
Elias Koutsoupias, Christos Papadimitriou, Worst-case equilibria symposium on theoretical aspects of computer science. pp. 404- 413 ,(1999) , 10.1007/3-540-49116-3_38
M. Charikar, S. Guha, Improved combinatorial algorithms for the facility location and k-median problems foundations of computer science. pp. 378- 388 ,(1999) , 10.1109/SFFCS.1999.814609
K. Jain, V.V. Vazirani, Primal-dual approximation algorithms for metric facility location and k-median problems foundations of computer science. pp. 2- 13 ,(1999) , 10.1109/SFFCS.1999.814571
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit, Local Search Heuristics for k -Median and Facility Location Problems SIAM Journal on Computing. ,vol. 33, pp. 544- 562 ,(2004) , 10.1137/S0097539702416402
Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract) symposium on the theory of computing. pp. 1- 10 ,(1999) , 10.1145/301250.301257
Tim Roughgarden, The price of anarchy is independent of the network topology symposium on the theory of computing. ,vol. 67, pp. 428- 437 ,(2002) , 10.1145/509907.509971
Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys, A constant-factor approximation algorithm for the k -median problem symposium on the theory of computing. ,vol. 65, pp. 129- 149 ,(2002) , 10.1006/JCSS.2002.1882
Tim Roughgarden, Éva Tardos, How bad is selfish routing? Journal of the ACM. ,vol. 49, pp. 236- 259 ,(2002) , 10.1145/506147.506153
Christos Papadimitriou, Algorithms, games, and the internet Proceedings of the thirty-third annual ACM symposium on Theory of computing - STOC '01. pp. 749- 753 ,(2001) , 10.1145/380752.380883
A. Vetta, Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions foundations of computer science. pp. 416- 425 ,(2002) , 10.1109/SFCS.2002.1181966