A primal-dual approximation algorithm for generalized Steiner network problems
From MaRDI portal
Recommendations
Cites work
- 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?)
- 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
- Survivable networks, linear programming relaxations and the parsimonious property
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
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
- A primal-dual approximation algorithm for the vertex cover P^3 problem
- Improved approximations for relative survivable network design
- Recent results on approximating the Steiner tree problem and its generalizations
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Online constrained forest and prize-collecting network design
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Primal-dual approximation algorithms for feedback problems in planar graphs
- A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
- Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
- 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
- Approximation of Steiner forest via the bidirected cut relaxation
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
- Approximating Steiner Networks with Node Weights
- Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements
- A primal-dual approximation algorithm for the Steiner forest problem
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
- Dimensioning multicast-enabled communications networks
- scientific article; zbMATH DE number 2086430 (Why is no real title available?)
- A variational approach to the Steiner network problem
- New primal-dual algorithms for Steiner tree problems
- Survivable network design for group connectivity in low-treewidth graphs
- LP-relaxations for tree augmentation
- Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
- Approximating minimum-power edge-covers and 2,3-connectivity
- Minimizing submodular functions over families of sets
- Integer plane multiflow maximisation: one-quarter-approximation and gaps
- Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems
- On survivable network polyhedra
- scientific article; zbMATH DE number 1532274 (Why is no real title available?)
- An efficient approximation algorithm for the survivable network design problem
- scientific article; zbMATH DE number 1670544 (Why is no real title available?)
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)
