A primal-dual approximation algorithm for generalized Steiner network problems
From MaRDI portal
Recommendations
Cites work
- 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
- scientific article; zbMATH DE number 1003253 (Why is no real title available?)
- scientific article; zbMATH DE number 1263259 (Why is no real title available?)
- scientific article; zbMATH DE number 1263260 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 742977 (Why is no real title available?)
- scientific article; zbMATH DE number 742979 (Why is no real title available?)
- Survivable networks, linear programming relaxations and the parsimonious property
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
Cited in
(50)- Approximating minimum-power edge-covers and 2,3-connectivity
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- An efficient approximation algorithm for the survivable network design problem
- A primal-dual approximation algorithm for the Steiner forest problem
- Recent results on approximating the Steiner tree problem and its generalizations
- LP-relaxations for tree augmentation
- Online constrained forest and prize-collecting network design
- On survivable network polyhedra
- Approximating minimum size \{1,2\}-connected networks
- A primal-dual approximation algorithm for the survivable network design problem in hypergraphs
- Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
- Minimizing submodular functions over families of sets
- A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
- Integer plane multiflow maximisation: one-quarter-approximation and gaps
- Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
- Approximation of Steiner forest via the bidirected cut relaxation
- scientific article; zbMATH DE number 1670544 (Why is no real title available?)
- An O( n)-competitive algorithm for online constrained forest problems
- Dimensioning multicast-enabled communications networks
- Approximation algorithms for multi-budgeted network design problems
- Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements
- scientific article; zbMATH DE number 1532274 (Why is no real title available?)
- Primal-dual approximation algorithms for feedback problems in planar graphs
- scientific article; zbMATH DE number 2086430 (Why is no real title available?)
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Greedy algorithms for online survivable network design
- Survivable network design for group connectivity in low-treewidth graphs
- Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
- Approximating Steiner Networks with Node Weights
- 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
- Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems
- Correlation clustering and two-edge-connected augmentation for planar graphs
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
- A primal-dual approximation algorithm for the vertex cover P^3 problem
- Improved approximations for relative survivable network design
- Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
- An approximation algorithm for minimum-cost vertex-connectivity problems
- A global analysis of the primal-dual method for edge augmentation problems
- Improved approximation algorithms for covering pliable set families and flexible graph connectivity
- Extending the primal-dual 2-approximation algorithm beyond uncrossable set families
- Extending the primal-dual 2-approximation algorithm beyond uncrossable set families
- Protecting the connectivity of a graph under non-uniform edge failures
- Protecting the connectivity of a graph under nonuniform edge failures
- Tight analysis of the primal-dual method for edge-covering pliable set families
- Tight guarantees for cut-relative survivable network design via a decomposition technique
- Improved approximation algorithms for capacitated network design and flexible graph connectivity
- A variational approach to the Steiner network problem
- New primal-dual algorithms for Steiner tree problems
- A factor 2 approximation algorithm for the generalized Steiner network problem
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)
