A constant factor approximation for the single sink edge installation problems

DOI10.1145/380752.380827zbMath1323.68568OpenAlexW2106676868MaRDI QIDQ5175993

Adam Meyerson, Sudipto Guha, Kamesh Munagala

Publication date: 27 February 2015

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

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (13)

LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design ⋮ Combinatorial approximation algorithms for buy-at-bulk connected facility location problems ⋮ Approximation Algorithms for Buy-at-Bulk Geometric Network Design ⋮ Connected facility location via random facility sampling and core detouring ⋮ Approximation to the Minimum Cost Edge Installation Problem ⋮ Approximation Algorithms for a Combined Facility Location Buy-at-Bulk Network Design Problem ⋮ Deterministic sampling algorithms for network design ⋮ A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design ⋮ Approximability of unsplittable shortest path routing problems ⋮ Oblivious Buy-at-Bulk in Planar Graphs ⋮ Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees ⋮ Improved approximation algorithms for the single-sink buy-at-bulk network design problems ⋮ A note on the subadditive network design problem

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: A constant factor approximation for the single sink edge installation problems