Cost-sharing mechanisms for network design

Anupam Gupta, Aravind Srinivasan, Éva Tardos

Research output: Contribution to journalArticlepeer-review


We consider a single-source network design problem from a game-theoretic perspective. Gupta, Kumar and Roughgarden (Proc. 35th Annual ACM STOC, pp. 365-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ál and Tardos (Proc. 44th Annual FOCS, pp. 584-593, 2003), and improves the previously-known approximation factor of 15 to 4.6.

Original languageEnglish (US)
Pages (from-to)98-119
Number of pages22
JournalAlgorithmica (New York)
Issue number1
StatePublished - Jan 2008

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Cost-sharing mechanisms for network design'. Together they form a unique fingerprint.

Cite this