A primal-dual approximation algorithm for generalized Steiner network problems
From MaRDI portal
Publication:1900190
DOI10.1007/BF01299747zbMath0838.90133OpenAlexW4385007144MaRDI QIDQ1900190
Milena Mihail, Vijay V. Vazirani, Michel X. Goemans, David P. Williamson
Publication date: 17 October 1995
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01299747
polynomial-time approximation algorithmsurvivable network designminimum-cost subgraphgeneralized Steiner network problem
Related Items
Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation, Primal-dual approximation algorithms for feedback problems in planar graphs, Approximation Algorithms for Multi-budgeted Network Design Problems, Minimizing submodular functions over families of sets, Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem, Correlation clustering and two-edge-connected augmentation for planar graphs, Approximation algorithms for flexible graph connectivity, Unnamed Item, Unnamed Item, LP-relaxations for tree augmentation, A primal-dual approximation algorithm for the vertex cover \(P^3\) problem, Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow, An O(logn)-Competitive Algorithm for Online Constrained Forest Problems, An approximation algorithm for minimum-cost vertex-connectivity problems, Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs, Online constrained forest and prize-collecting network design, On survivable network polyhedra, A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs, Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems, Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements, Approximation of Steiner forest via the bidirected cut relaxation, Approximating Steiner Networks with Node Weights, A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs, Approximating minimum-power edge-covers and 2,3-connectivity, Recent results on approximating the Steiner tree problem and its generalizations, An efficient approximation algorithm for the survivable network design problem, Integer plane multiflow maximisation: one-quarter-approximation and gaps, Approximating minimum size \{1,2\}-connected networks, A primal-dual approximation algorithm for the survivable network design problem in hypergraphs, Dimensioning multicast-enabled communications networks
Cites Work
- Survivable networks, linear programming relaxations and the parsimonious property
- A fast approximation algorithm for the multicovering problem
- An 11/6-approximation algorithm for the network Steiner problem
- Approximation Algorithms for Several Graph Augmentation Problems
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
