@article {17581,
title = {Cost-Sharing Mechanisms for Network Design},
journal = {Algorithmica},
volume = {50},
year = {2008},
month = {2008///},
pages = {98 - 119},
abstract = {We consider a single-source network design problem from a game-theoretic perspective. Gupta, Kumar and Roughgarden (Proc. 35th Annual ACM STOC, pp. 365{\textendash}372, 2003 ) developed a simple method for a single-source rent-or-buy problem that also yields the best-known approximation ratio for the problem. We show how to use a variant of this method to develop an approximately budget-balanced and group strategyproof cost-sharing method for the problem. The novelty of our approach stems from our obtaining the cost-sharing methods for the rent-or-buy problem by carefully combining cost-shares for the simpler Steiner tree problem. Our algorithm is conceptually simpler than the previous such cost-sharing method due to P{\'a}l and Tardos (Proc. 44th Annual FOCS, pp. 584{\textendash}593, 2003 ), and improves the previously-known approximation factor of 15 to 4.6.},
isbn = {0178-4617},
url = {http://dx.doi.org/10.1007/s00453-007-9065-y},
author = {Gupta,Anupam and Srinivasan, Aravind and Tardos,{\'E}va}
}