Approximation via cost sharing
From MaRDI portal
Publication:3546337
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
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