Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

DOI10.1007/B99805zbMATH Open1105.68304OpenAlexW4301133941MaRDI QIDQ5313017FDOQ5313017

Authors: Anupam Gupta, Aravind Srinivasan, Éva Tardos 

Publication date: 25 August 2005

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b99805

Recommendations

• Cost-sharing mechanisms for network design
• Approximation via cost sharing
• Optimal Efficiency Guarantees for Network Design Mechanisms
• On cost sharing mechanisms in the network design game
• Approximation and Online Algorithms

Mathematics Subject Classification ID

Applications of game theory (91A80) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

Cited In (19)

• On cost sharing mechanisms in the network design game
• On cost allocation in communication networks
• Black-box reductions for cost-sharing mechanism design
• The warehouse-retailer network design game
• A quadratic time exact algorithm for continuous connected 2-facility location problem in trees (extended abstract)
• A quadratic time exact algorithm for continuous connected 2-facility location problem in trees
• Optimal Efficiency Guarantees for Network Design Mechanisms
• Approximation via cost sharing
• Cost allocation protocols for supply contract design in network situations
• Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems
• Fair cost-sharing methods for scheduling jobs on parallel machines
• Complexity of constructing solutions in the core based on synergies among coalitions
• Cross-monotonic cost sharing methods for connected facility location games
• A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
• Connected facility location via random facility sampling and core detouring
• Strategic sharing of a costly network
• Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
• Cost-sharing mechanisms for network design
• From packing rules to cost-sharing mechanisms

This page was built for publication: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

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