A constant factor approximation for the single sink edge installation problems

DOI10.1145/380752.380827MaRDI QIDQ5175993zbMATH OpenOpenAlexFDO

Authors Sudipto Guha, Adam Meyerson, 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)

Recommendations

• A constant factor approximation for the single sink edge installation problem
• Improved Approximation for Single-Sink Buy-at-Bulk
• scientific article; zbMATH DE number 2086941
• Approximating the single-sink link-installation problem in network design
• Cost-Distance: Two Metric Network Design

Cites work

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

Cited in

(16)

• Approximating the single-sink link-installation problem in network design
• Deterministic sampling algorithms for network design
• Approximation to the Minimum Cost Edge Installation Problem
• Oblivious buy-at-bulk in planar graphs
• A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design
• Approximability of unsplittable shortest path routing problems
• Combinatorial approximation algorithms for buy-at-bulk connected facility location problems
• scientific article; zbMATH DE number 2086941 (Why is no real title available?)
• 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
• A constant factor approximation for the single sink edge installation problem
• Approximation algorithms for a combined facility location buy-at-bulk network design problem
• Connected facility location via random facility sampling and core detouring
• Approximation Algorithms for Buy-at-Bulk Geometric Network Design
• LP-based approximation algorithms for facility location in buy-at-bulk network design

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175993)