When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

DOI10.1137/S0097539792236237zbMath0831.68071OpenAlexW2011823863MaRDI QIDQ4842113

Ajit Agrawal, R. Ravi, Philip N. Klein

Publication date: 26 July 1995

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

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

zbMATH Keywords

network designgeneralized network Steiner problem

Mathematics Subject Classification ID

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

Related Items (82)

Beyond Moulin mechanisms ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ On-line generalized Steiner problem ⋮ Service-constrained network design problems ⋮ Unnamed Item ⋮ Primal-dual approximation algorithms for feedback problems in planar graphs ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online ⋮ Resource allocation problem under single resource assignment ⋮ Minimum-Cost Network Design with (Dis)economies of Scale ⋮ New primal-dual algorithms for Steiner tree problems ⋮ An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties ⋮ Chvátal-Gomory cuts for the Steiner tree problem ⋮ On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ A Spectral Approach to Network Design ⋮ Approximation algorithms for Steiner forest: An experimental study ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ Primal-Dual Schema for Capacitated Covering Problems ⋮ A fast approximation algorithm for the maximum 2-packing set problem on planar graphs ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ Pruning 2-connected graphs ⋮ A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem ⋮ Bayesian generalized network design ⋮ LP-Based Algorithms for Capacitated Facility Location ⋮ A PTAS for the Steiner Forest Problem in Doubling Metrics ⋮ Connected facility location via random facility sampling and core detouring ⋮ Static Routing in Stochastic Scheduling: Performance Guarantees and Asymptotic Optimality ⋮ A Local-Search Algorithm for Steiner Forest ⋮ Stronger MIP formulations for the Steiner forest problem ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ An Exact Algorithm for the Steiner Forest Problem ⋮ Approximation Algorithms for Single and Multi-Commodity Connected Facility Location ⋮ A simpler and better derandomization of an approximation algorithm for single source rent-or-buy ⋮ An O(logn)-Competitive Algorithm for Online Constrained Forest Problems ⋮ An approximation algorithm for minimum-cost vertex-connectivity problems ⋮ Complexity of minimum irreducible infeasible subsystem covers for flow networks ⋮ Online constrained forest and prize-collecting network design ⋮ Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem ⋮ Elementary approximation algorithms for prize collecting Steiner tree problems ⋮ A partition-based relaxation for Steiner trees ⋮ Online Node-weighted Steiner Forest and Extensions via Disk Paintings ⋮ The Steiner forest problem revisited ⋮ Unnamed Item ⋮ A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem ⋮ On survivable network polyhedra ⋮ A genetic algorithm for the maximum 2-packing set problem ⋮ Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements ⋮ Probabilistic models for the Steiner Tree problem ⋮ Approximation of Steiner forest via the bidirected cut relaxation ⋮ Parameterized certificate dispersal and its variants ⋮ Cluster before you hallucinate: node-capacitated network design and energy efficient routing ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ Improved approximations for two-stage MIN-cut and shortest path problems under uncertainty ⋮ Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions ⋮ Approximating Steiner Networks with Node Weights ⋮ Group-Strategyproof Cost Sharing for Metric Fault Tolerant Facility Location ⋮ Approximating Survivable Networks with Minimum Number of Steiner Points ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ An approximation algorithm to the \(k\)-Steiner forest problem ⋮ Algorithms for the metric ring star problem with fixed edge-cost ratio ⋮ Primal-dual schema for capacitated covering problems ⋮ Non-cooperative tree creation ⋮ Approximation algorithms for soft-capacitated facility location in capacitated network design ⋮ On the Complexity of Local Graph Transformations ⋮ Combinatorial optimization in system configuration design ⋮ Recent results on approximating the Steiner tree problem and its generalizations ⋮ Graphs and Algorithms in Communication Networks on Seven League Boots ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems ⋮ An efficient approximation algorithm for the survivable network design problem ⋮ Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ Algorithms for a multi-level network optimization problem ⋮ Unnamed Item ⋮ On the Clustered Steiner Tree Problem ⋮ On the Generalized Steiner Problem with Network Reliability Conditions ⋮ On the clustered Steiner tree problem

This page was built for publication: When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks