A primal-dual approximation algorithm for generalized Steiner network problems
From MaRDI portal
Publication:1900190
DOI10.1007/BF01299747zbMATH Open0838.90133OpenAlexW4385007144MaRDI QIDQ1900190FDOQ1900190
Authors: David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani 
Publication date: 17 October 1995
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01299747
Recommendations
survivable network designpolynomial-time approximation algorithmminimum-cost subgraphgeneralized Steiner network problem
Cites Work
- Title not available (Why is that?)
- A fast approximation algorithm for the multicovering problem
- An 11/6-approximation algorithm for the network Steiner problem
- Title not available (Why is that?)
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Title not available (Why is that?)
- Title not available (Why is that?)
- Survivable networks, linear programming relaxations and the parsimonious property
- Title not available (Why is that?)
- Approximation Algorithms for Several Graph Augmentation Problems
- Title not available (Why is that?)
Cited In (41)
- Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
- An approximation algorithm for minimum-cost vertex-connectivity problems
- Improved approximations for relative survivable network design
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Recent results on approximating the Steiner tree problem and its generalizations
- Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
- Online constrained forest and prize-collecting network design
- Primal-dual approximation algorithms for feedback problems in planar graphs
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
- Approximation algorithms for multi-budgeted network design problems
- An \(O(\log n)\)-competitive algorithm for online constrained forest problems
- Greedy algorithms for online survivable network design
- Correlation clustering and two-edge-connected augmentation for planar graphs
- Approximating minimum size \{1,2\}-connected networks
- Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
- A primal-dual approximation algorithm for the survivable network design problem in hypergraphs
- On the solution of the generalized steiner problem by the subgradient method
- Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
- Approximation of Steiner forest via the bidirected cut relaxation
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Approximating Steiner Networks with Node Weights
- Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
- A primal-dual approximation algorithm for the Steiner forest problem
- Dimensioning multicast-enabled communications networks
- Title not available (Why is that?)
- A variational approach to the Steiner network problem
- Survivable network design for group connectivity in low-treewidth graphs
- New primal-dual algorithms for Steiner tree problems
- LP-relaxations for tree augmentation
- Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
- Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems
- Integer plane multiflow maximisation: one-quarter-approximation and gaps
- Approximating minimum-power edge-covers and 2,3-connectivity
- Minimizing submodular functions over families of sets
- Title not available (Why is that?)
- On survivable network polyhedra
- An efficient approximation algorithm for the survivable network design problem
- Title not available (Why is that?)
This page was built for publication: A primal-dual approximation algorithm for generalized Steiner network problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1900190)
