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