O (log 2 k / log log k )-approximation algorithm for directed Steiner tree

DOI10.1145/3313276.3316349zbMath1433.68614arXiv1811.03020OpenAlexW2900307033MaRDI QIDQ5212767

Shi Li, Fabrizio Grandoni, Bundit Laekhanukit

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.03020

zbMATH Keywords

Sherali-Adams hierarchydirected Steiner treequasi-polynomial time

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (10)

Bounded Degree Group Steiner Tree Problems ⋮ On approximating degree-bounded network design problems ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ A Spectral Approach to Network Design ⋮ Navigational guidance -- a deep learning approach ⋮ Approximation algorithms for priority Steiner tree problems ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Tight bounds on subexponential time approximation of set cover and related problems

This page was built for publication: O (log ² k / log log k )-approximation algorithm for directed Steiner tree