Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
From MaRDI portal
Recommendations
- A constant-factor approximation for stochastic Steiner forest
- Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
- Automata, Languages and Programming
- A 4-approximation algorithm for k-prize collecting Steiner tree problems
- Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
Cites work
- Title not available (Why is no real title available?)
- scientific article; zbMATH DE number 1445375 (Why is no real title available?)
- 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
- A General Approximation Technique for Constrained Forest Problems
- A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
- A faster approximation algorithm for the Steiner tree problem in graphs
- A faster implementation of the Goemans-Williamson clustering algorithm
- A note on the prize collecting traveling salesman problem
- A primal-dual approximation algorithm for Min-sum single-machine scheduling problems
- A primal-dual approximation algorithm for generalized Steiner network problems
- A primal-dual approximation algorithm for the facility location problem with submodular penalties
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Efficient probabilistically checkable proofs and applications to approximations
- Hedging uncertainty: approximation algorithms for stochastic optimization problems
- Improved approximation algorithms for prize-collecting Steiner tree and TSP
- New approximation algorithms for the Steiner tree problems
- Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
- Reducibility among combinatorial problems
- Sampling and cost-sharing: approximation algorithms for stochastic optimization problems
- Scenario reduction algorithms in stochastic programming
- Steiner Minimal Trees
- Steiner tree approximation via iterative randomized rounding
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The Steiner problem with edge lengths 1 and 2
- The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
- Thek-Steiner Ratio in Graphs
- Tighter Bounds for Graph Steiner Tree Approximation
- Two‐stage stochastic integer programming: a survey
Cited in
(3)
This page was built for publication: Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2165784)
