Elementary approximation algorithms for prize collecting Steiner tree problems
DOI10.1016/J.IPL.2007.12.010zbMATH Open1192.68901OpenAlexW2055226597MaRDI QIDQ963393FDOQ963393
Authors: Shai Gutner 
Publication date: 19 April 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2007.12.010
Recommendations
- Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
- A primal-dual algorithm for the generalized prize-collecting Steiner forest problem
- Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
- Improved approximation algorithms for prize-collecting Steiner tree and TSP
- scientific article; zbMATH DE number 1445375
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- A General Approximation Technique for Constrained Forest Problems
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- A note on the prize collecting traveling salesman problem
- Title not available (Why is that?)
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- A unified approach to approximating resource allocation and scheduling
- Network design for information networks
- One for the price of two: a unified approach for approximating covering problems
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- A group-strategyproof mechanism for Steiner forests
- An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem
- Approximation algorithms for prize collecting forest problems with submodular penalty functions
Cited In (20)
- Approximation algorithms for prize collecting forest problems with submodular penalty functions
- Prize-collecting Steiner network problems
- Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
- Variations of the prize‐collecting Steiner tree problem
- Title not available (Why is that?)
- An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties
- A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
- Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
- Approximation algorithms for group prize-collecting and location-routing problems
- Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
- Euclidean prize-collecting Steiner forest
- An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
- Improved approximation algorithms for prize-collecting Steiner tree and TSP
- A primal-dual approximation algorithm for the Steiner forest problem
- A local-search algorithm for Steiner forest
- On the integrality gap of the prize-collecting Steiner forest LP
- A primal-dual algorithm for the generalized prize-collecting Steiner forest problem
- A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems
- A 2-approximation for the \(k\)-prize-collecting Steiner tree problem
- A General Approximation Technique for Constrained Forest Problems
This page was built for publication: Elementary approximation algorithms for prize collecting Steiner tree problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q963393)
