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: |
Logarithm
Open problem 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Management Science and Operations Research 01 natural sciences Industrial and Manufacturing Engineering Combinatorics Polyhedron Polymatroid Congestion game Mathematics Discrete mathematics 021103 operations research Applied Mathematics ALGORITHMS Approximation algorithm Base (topology) Ackermann function WELFARE MAXIMIZATION 010201 computation theory & mathematics matroid Software |
| 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 |
| Externí odkaz: |
|
Full Text from ScienceDirect