$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm

DOI10.1137/20M1312988OpenAlexW2949193238WikidataQ114074219 ScholiaQ114074219MaRDI QIDQ5890148

Fabrizio Grandoni, Bundit Laekhanukit, Shi Li

Publication date: 28 April 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1312988

zbMATH Keywords

network designapproximation algorithmshardness of approximationdirected Steiner tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• Approximating fault-tolerant group-Steiner problems
• Approximating the weight of shallow Steiner trees
• An 11/6-approximation algorithm for the network Steiner problem
• A greedy approximation algorithm for the group Steiner problem
• An improved approximation scheme for the Group Steiner Problem
• Polylogarithmic inapproximability
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Approximating Directed Steiner Problems via Tree Embedding
• Approximation Algorithms for Directed Steiner Problems
• Approximating Rooted Steiner Networks
• Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
• MaxMin allocation via degree lower-bounded arborescences
• Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time
• Tighter Bounds for Graph Steiner Tree Approximation
• A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
• On Survivable Set Connectivity
• Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
• Steiner Tree Approximation via Iterative Randomized Rounding
• Linear Programming Hierarchies Suffice for Directed Steiner Tree
• How to Sell Hyperedges: The Hypermatching Assignment Problem
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm