$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
type: Item
instance of: scholarly article
title: $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
DOI: 10.1137/20M1312988
author: Fabrizio Grandoni
author: B. Laekhanukit
author: Shi Li
published in: SIAM Journal on Computing
publication date: 2023-04-28T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7680893
zbMATH Keywords: approximation algorithms
zbMATH Keywords: hardness of approximation
zbMATH Keywords: network design
zbMATH Keywords: directed Steiner tree
MaRDI profile type: MaRDI publication profile
Wikidata QID: Q114074219
full work available at URL: 20m1312988
OpenAlex ID: W2949193238
cites work: MaxMin allocation via degree lower-bounded arborescences
cites work: Steiner Tree Approximation via Iterative Randomized Rounding
cites work: On Survivable Set Connectivity
cites work: Approximation Algorithms for Directed Steiner Problems
cites work: Q4542528
cites work: A greedy approximation algorithm for the group Steiner problem
cites work: Approximating Rooted Steiner Networks
cites work: How to Sell Hyperedges: The Hypermatching Assignment Problem
cites work: A tight bound on approximating arbitrary metrics by tree metrics
cites work: Linear Programming Hierarchies Suffice for Directed Steiner Tree
cites work: A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
cites work: Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time
cites work: Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
cites work: Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree
cites work: Q5417728
cites work: Polylogarithmic inapproximability
cites work: An improved approximation scheme for the Group Steiner Problem
cites work: Approximating fault-tolerant group-Steiner problems
cites work: Approximating the weight of shallow Steiner trees
cites work: Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
cites work: Approximating Directed Steiner Problems via Tree Embedding
cites work: A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
cites work: Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
cites work: Q5111409
cites work: Q2941638
cites work: Tighter Bounds for Graph Steiner Tree Approximation
cites work: An 11/6-approximation algorithm for the network Steiner problem
cites work: A series of approximation algorithms for the acyclic directed Steiner tree problem
cites work: Q4828915
Recommended article: O (log 2 k / log log k )-approximation algorithm for directed Steiner tree
Recommended article: Multi-rooted greedy approximation of directed Steiner trees with applications
Recommended article: Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications
Recommended article: Approximating Directed Steiner Problems via Tree Embedding
Recommended article: Approximation Algorithms for Directed Steiner Problems
description: scientific article; zbMATH DE number 7680893