Cross-monotonic cost sharing methods for connected facility location games

DOI10.1016/j.tcs.2004.07.033zbMath1071.90023OpenAlexW2625256146MaRDI QIDQ703566

Guido Schäfer, Stefano Leonardi

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.07.033

zbMATH Keywords

approximation algorithmsmechanism designconnected facility locationcost sharing mechanisms

Mathematics Subject Classification ID

Games involving graphs (91A43) Discrete location and assignment (90B80) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Randomized algorithms (68W20)

Related Items

Beyond Moulin mechanisms, Non-cooperative capacitated facility location games, Cost-sharing mechanisms for scheduling under general demand settings, Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems, Black-box reductions for cost-sharing mechanism design, Cost-sharing mechanisms for network design, A cross-monotonic cost sharing method for the facility location game with service installation costs, OPEN PROBLEMS IN COOPERATIVE LOCATION GAMES, Unnamed Item

Cites Work

• Unnamed Item
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Simpler and better approximation algorithms for network design
• Applications of approximation algorithms to cooperative games
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Optimum branchings
• Strategyproof sharing of submodular costs: budget balance versus efficiency