Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

DOI10.1007/B99805MaRDI QIDQ5313017zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(19)

• On cost allocation in communication networks
• On cost sharing mechanisms in the network design game
• 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
• Cross-monotonic cost sharing methods for connected facility location games
• Complexity of constructing solutions in the core based on synergies among coalitions
• A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
• Strategic sharing of a costly network
• Connected facility location via random facility sampling and core detouring
• 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)