A constant factor approximation for the single sink edge installation problems

DOI10.1145/380752.380827zbMATH Open1323.68568OpenAlexW2106676868MaRDI QIDQ5175993FDOQ5175993

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

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

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)

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
• Title not available (Why is that?)
• Combinatorial approximation algorithms for buy-at-bulk connected facility location problems
• 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)