Steiner Tree Approximation via Iterative Randomized Rounding
From MaRDI portal
Publication:5395705
DOI10.1145/2432622.2432628zbMath1281.68234OpenAlexW1976584101MaRDI QIDQ5395705
Laura Sanità, Thomas Rothvoß, Fabrizio Grandoni, Jaroslaw Byrka
Publication date: 17 February 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2432622.2432628
Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (93)
Improved Approximation Algorithms for Inventory Problems ⋮ $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties ⋮ Approximating Steiner Trees and Forests with Minimum Number of Steiner Points ⋮ Steiner Trees with Bounded RC-Delay ⋮ Unnamed Item ⋮ Improved algorithms for joint optimization of facility locations and network connections ⋮ A robust and scalable algorithm for the Steiner problem in graphs ⋮ The Influence of Preprocessing on Steiner Tree Approximations ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ A practical greedy approximation for the directed Steiner tree problem ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs ⋮ Approximating activation edge-cover and facility location problems ⋮ Chvátal-Gomory cuts for the Steiner tree problem ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ Growing Half-Balls: Minimizing Storage and Communication Costs in Content Delivery Networks ⋮ A Practical Greedy Approximation for the Directed Steiner Tree Problem ⋮ A Spectral Approach to Network Design ⋮ Robust reoptimization of Steiner trees ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ On the lossy kernelization for connected treedepth deletion set ⋮ On the complexity of the cable-trench problem ⋮ Stronger path‐based extended formulation for the Steiner tree problem ⋮ A linear programming based approach to the Steiner tree problem with a fixed number of terminals ⋮ Universal Algorithms for Clustering Problems ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ The Clustered Selected-Internal Steiner Tree Problem ⋮ Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ On the Price of Stability of Undirected Multicast Games ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Multi-priority graph sparsification ⋮ Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm ⋮ Bayesian generalized network design ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Approximation algorithms for priority Steiner tree problems ⋮ Local Search Based Approximation Algorithms for Two-Stage Stochastic Location Problems ⋮ A primal-dual algorithm for the generalized prize-collecting Steiner forest problem ⋮ Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover ⋮ Combination algorithms for Steiner tree variants ⋮ Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ Strong Steiner Tree Approximations in Practice ⋮ Stronger MIP formulations for the Steiner forest problem ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ A Weighted Linear Matroid Parity Algorithm ⋮ The Bursty Steiner Tree Problem ⋮ An improved algorithm for the Steiner tree problem with bounded edge-length ⋮ Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming ⋮ Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Covering problems in edge- and node-weighted graphs ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ Steiner trees with bounded RC-delay ⋮ Unnamed Item ⋮ Computing a tree having a small vertex cover ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Unnamed Item ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Improved approximation algorithms for minimum power covering problems ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ Improved approximations for two-stage MIN-cut and shortest path problems under uncertainty ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Two-level hub Steiner trees ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Multi-level Steiner Trees ⋮ On approximate preprocessing for domination and hitting subgraphs with connected deletion sets ⋮ Unnamed Item ⋮ Efficient Black-Box Reductions for Separable Cost Sharing ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems ⋮ Exploring the Tractability of the Capped Hose Model ⋮ Lossy Kernels for Hitting Subgraphs ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ A 3/2-approximation algorithm for some minimum-cost graph problems ⋮ A 2-approximation for the \(k\)-prize-collecting Steiner tree problem ⋮ On full Steiner trees in unit disk graphs ⋮ Multi-Level Steiner Trees. ⋮ Approximation algorithms for connectivity augmentation problems ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ An improved approximation algorithm for the uniform cost-distance Steiner tree problem ⋮ Multi-rooted greedy approximation of directed Steiner trees with applications
This page was built for publication: Steiner Tree Approximation via Iterative Randomized Rounding
