A logarithmic approximation for polymatroid congestion games

T. Harks, T. Oosterwijk, T. Vredeveld

Research output: Contribution to JournalArticleAcademicpeer-review


© 2016 Elsevier B.V.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ρ-approximation algorithm, where ρ is the sum of the ranks of the polymatroids and Hρ denotes the ρ-th harmonic number. The approximation guarantee is best possible up to a constant factor and solves an open problem of Ackermann et al. (2008).
Original languageEnglish
Pages (from-to)712-717
JournalOperations Research Letters
Issue number6
Publication statusPublished - 1 Nov 2016
Externally publishedYes


Dive into the research topics of 'A logarithmic approximation for polymatroid congestion games'. Together they form a unique fingerprint.

Cite this