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

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

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

(17)

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

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)