@inbook{02eb0e889ec640b2b5786a58d582857f,
title = "Cost-sharing mechanisms for network design",
abstract = "We consider a single source network design problem from a game-theoretic perspective. Gupta, Kumar and Roughgarden (Proc. 35th Annual ACM STOC, pages 365-372, 2003) developed a simple method for 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 problem Steiner tree problem; we feel that this idea may have wider implications. Our algorithm is conceptually simpler than the previous such cost-sharing method due to Pal and Tardos (Proc. 44th Annual FOCS, pages 584-593, 2003), and has a much improved approximation factor of 4.6 (over the previously known factor of 15).",
author = "Anupam Gupta and Aravind Srinivasan and {\'E}va Tardos",
year = "2004",
doi = "10.1007/978-3-540-27821-4_13",
language = "English (US)",
isbn = "3540228942",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "139--150",
editor = "Klaus Jansen and Sanjeev Khanna and Rolim, {Jose D. P.} and Dana Ron",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
}