Approximation via cost sharing

DOI10.1145/1236457.1236458zbMath1216.68339MaRDI 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

68M10: Network design and communication in computer systems

68W25: Approximation algorithms

Related Items

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