A Logarithmic Approximation for Polymatroid Congestion Games

Autor: Tobias Harks, Tjark Vredeveld, Tim Oosterwijk
Přispěvatelé: RS: GSBE ETBC, QE Operations research
Jazyk: angličtina
Rok vydání: 2016
Předmět:
Zdroj: Operations Research Letters, 44(6), 712-717. Elsevier Science
ISSN: 0167-6377
Popis: 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.
Databáze: OpenAIRE
Pro tento záznam nejsou dostupné žádné jednotky.