A Logarithmic Approximation for Polymatroid Congestion Games

Tobias Harks, Tim Oosterwijk*, Tjark Vredeveld

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

314 Downloads (Pure)

Abstract

We study the problem of computing a social optimum in polymatroid congestion games, where the strategy space of every player consists of a player-specific integral polymatroid base polyhedron on a set of resources. For non-decreasing cost functions we devise an H-rho-approximation algorithm, where rho is the sum of the ranks of the polymatroids and H-rho denotes the rho-th harmonic number. The approximation guarantee is best possible up to a constant factor and solves an open problem of Ackermann et al. (2008). (C) 2016 Elsevier B.V. All rights reserved.

Original languageEnglish
Pages (from-to)712-717
Number of pages6
JournalOperations Research Letters
Volume44
Issue number6
DOIs
Publication statusPublished - Nov 2016

Keywords

  • Congestion game
  • approximation algorithm
  • polymatroid
  • matroid
  • Matroid
  • WELFARE MAXIMIZATION
  • ALGORITHMS
  • Approximation algorithm
  • Polymatroid

Cite this