Simpler and better approximation algorithms for network design

DOI10.1145/780542.780597zbMath1192.90226OpenAlexW2079936083MaRDI QIDQ3581250

Tim Roughgarden, Anupam Gupta, Amit Kumar

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780597

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Network design and communication in computer systems (68M10) Approximation algorithms (68W25)

Related Items (30)

On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Incremental network design with shortest paths ⋮ A quadratic time exact algorithm for continuous connected 2-facility location problem in trees ⋮ Combinatorial approximation algorithms for buy-at-bulk connected facility location problems ⋮ Approximation Algorithms for Buy-at-Bulk Geometric Network Design ⋮ Design of trees in the hose model: the balanced case ⋮ Online Buy-at-Bulk Network Design ⋮ Competitive and deterministic embeddings of virtual networks ⋮ A Quadratic Time Exact Algorithm for Continuous Connected 2-Facility Location Problem in Trees (Extended Abstract) ⋮ Connected facility location via random facility sampling and core detouring ⋮ Exact Approaches for Designing Multifacility Buy-at-Bulk Networks ⋮ An exact algorithm for the maximum leaf spanning tree problem ⋮ A simpler and better derandomization of an approximation algorithm for single source rent-or-buy ⋮ Cost-sharing mechanisms for network design ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Deterministic sampling algorithms for network design ⋮ Cross-monotonic cost sharing methods for connected facility location games ⋮ A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design ⋮ Hardness of robust network design ⋮ Approximability of unsplittable shortest path routing problems ⋮ Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph ⋮ Algorithms for the metric ring star problem with fixed edge-cost ratio ⋮ Approximation algorithms for connected facility location problems ⋮ Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees ⋮ Two-level hub Steiner trees ⋮ Improved approximation algorithms for the single-sink buy-at-bulk network design problems ⋮ A note on the subadditive network design problem ⋮ Provisioning virtual private networks under traffic uncertainty ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Simpler and better approximation algorithms for network design