Approximation via cost sharing

DOI10.1145/1236457.1236458MaRDI QIDQ3546337zbMATHOpenAlexFDO

Authors Anupam Gupta, Amit Kumar, Martin Pál, Tim Roughgarden

Publication date 21 December 2008

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1236457.1236458

Mathematics Subject Classification ID

Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

Recommendations

• Cost-sharing mechanisms for network design
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Simpler and better approximation algorithms for network design
• Strict cost sharing schemes for Steiner forest
• Approximation algorithms for nonuniform buy-at-bulk network design

Cited in

(28)

• Group parking permit problems
• A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
• Minimizing Rosenthal potential in multicast games
• Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
• Multi-priority online scheduling with cancellations
• Exploring the tractability of the capped hose model
• Design is as easy as optimization
• Designing networks with good equilibria under uncertainty
• Minimum-cost network design with (dis)economies of scale
• Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
• Cluster before you hallucinate: node-capacitated network design and energy efficient routing
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Combinatorial optimization in system configuration design
• Network design via core detouring for problems without a core
• Deterministic sampling algorithms for network design
• Hallucination helps: energy efficient virtual circuit routing
• Cost-sharing mechanisms for network design
• A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
• Sharing the cost more efficiently, improved approximation for multicommodity rent-or-buy
• Connected facility location via random facility sampling and core detouring
• Competitive Cost Sharing with Economies of Scale
• A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design
• Simpler and better approximation algorithms for network design
• Strict cost sharing schemes for Steiner forest
• Competitive cost sharing with economies of scale
• Two-stage stochastic max-weight independent set problems
• Towards flexible demands in online leasing problems
• Approximating some network design problems with node costs

This page was built for publication: Approximation via cost sharing

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