A logarithmic approximation for polymatroid congestion games

DOI10.1016/J.ORL.2016.09.001MaRDI QIDQ1709937zbMATH OpenOpenAlexFDO

Authors Tobias Harks, Tim Oosterwijk, T. Vredeveld

Publication date 15 January 2019

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://cris.maastrichtuniversity.nl/en/publications/21d94606-76a7-4bc4-99ac-be397aa4b951

zbMATH Keywords

approximation algorithmcongestion gamematroidpolymatroid

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Traffic problems in operations research (90B20) Combinatorial optimization (90C27) Noncooperative games (91A10)

Recommendations

• Finding social optima in congestion games with positive externalities
• Efficiency of equilibria in uniform matroid congestion games
• Computation and efficiency of potential function minimizers of combinatorial congestion games
• Totally unimodular congestion games
• Bounding the potential function in congestion games and approximate pure Nash equilibria

Cites work

• A class of games possessing pure-strategy Nash equilibria
• A threshold of ln n for approximating set cover
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• An analysis of the greedy algorithm for the submodular set covering problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Buy-at-bulk network design with protection
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing pure Nash and strong equilibria in bottleneck congestion games
• Congestion games with player-specific payoff functions
• Finding minimum congestion spanning trees
• Finding social optima in congestion games with positive externalities
• How hard is it to find extreme Nash equilibria in network congestion games?
• How to find Nash equilibria with extreme total latency in network congestion games?
• scientific article; zbMATH DE number 5485547 (Why is no real title available?)
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Minimum-cost network design with (dis)economies of scale
• On the impact of combinatorial structure on congestion games
• Optimal cost sharing for capacitated facility location games
• Optimal cost sharing for resource selection games
• Resource competition on integral polymatroids
• Structure preserving reductions among convex optimization problems
• Submodular functions and optimization.
• The complexity of pure Nash equilibria
• The complexity of welfare maximization in congestion games
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region

Cited in

(4)

• A game theoretic approach to a problem in polymatroid maximization
• Approximate separable multichoice optimization over monotone systems
• Finding social optima in congestion games with positive externalities
• Sensitivity analysis for convex separable optimization over integral polymatroids

This page was built for publication: A logarithmic approximation for polymatroid congestion games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709937)