On the approximability of some network design problems

DOI10.1145/1361192.1361200zbMath1445.68156OpenAlexW2166747457MaRDI QIDQ4962716

Anupam Gupta, Joseph (Seffi) Naor, Julia Chuzhoy, Amitabh Sinha

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

network designhardness of approximationpriority Steiner treefixed-charge network flowcost-distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (10)

Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ Unnamed Item ⋮ Multi-priority graph sparsification ⋮ Approximation algorithms for priority Steiner tree problems ⋮ On a class of branching problems in broadcasting and distribution ⋮ A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design ⋮ Multi-level Steiner Trees ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems ⋮ Multi-Level Steiner Trees. ⋮ An improved approximation algorithm for the uniform cost-distance Steiner tree problem

This page was built for publication: On the approximability of some network design problems