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 (19)

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

This page was built for publication: Approximation via cost sharing