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 (27)
- Simpler and better approximation algorithms for network design
- Multi-Priority Online Scheduling with Cancellations
- Competitive Cost Sharing with Economies of Scale
- Deterministic sampling algorithms for network design
- Exploring the Tractability of the Capped Hose Model
- A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design
- Towards flexible demands in online leasing problems
- 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
- Designing Networks with Good Equilibria under Uncertainty
- Minimum-Cost Network Design with (Dis)economies of Scale
- 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
- Dynamic vs. oblivious routing in network design
- 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
- Hallucination Helps: Energy Efficient Virtual Circuit Routing
- Design is as easy as optimization
- Two-stage stochastic max-weight independent set problems
- Cluster before you hallucinate: node-capacitated network design and energy efficient routing
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)
