Approximation via cost sharing

DOI10.1145/1236457.1236458zbMath1216.68339OpenAlexW2096881311MaRDI QIDQ3546337

Martin Pál, Amit Kumar, Anupam Gupta, 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

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

Related Items

Two-stage stochastic max-weight independent set problems, Minimum-Cost Network Design with (Dis)economies of Scale, Group parking permit problems, Dynamic vs. oblivious routing in network design, Connected facility location via random facility sampling and core detouring, Minimizing Rosenthal potential in multicast games, Approximation Algorithms for Single and Multi-Commodity Connected Facility Location, A simpler and better derandomization of an approximation algorithm for single source rent-or-buy, Towards flexible demands in online leasing problems, Deterministic sampling algorithms for network design, Competitive cost sharing with economies of scale, A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design, A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem, Competitive Cost Sharing with Economies of Scale, Hallucination Helps: Energy Efficient Virtual Circuit Routing, Designing Networks with Good Equilibria under Uncertainty, Multi-Priority Online Scheduling with Cancellations, Combinatorial optimization in system configuration design, Exploring the Tractability of the Capped Hose Model