Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
From MaRDI portal
Publication:2379971
DOI10.1016/j.ipl.2007.03.012zbMath1184.68633OpenAlexW2099618932MaRDI QIDQ2379971
Cristina G. Fernandes, José C. de Pina, Paulo Feofiloff, Carlos E. Ferreira
Publication date: 24 March 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2007.03.012
Related Items
Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ On the Exact Solution of Prize-Collecting Steiner Tree Problems ⋮ Risk models for the prize collecting Steiner tree problems with interval data ⋮ Complexity and approximation for traveling salesman problems with profits ⋮ A fast prize-collecting Steiner forest algorithm for functional analyses in biological networks ⋮ Approximation algorithms for group prize-collecting and location-routing problems ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An efficient approximation algorithm for the survivable network design problem
- A data structure for bicategories, with application to speeding up an approximation algorithm
- Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
- A General Approximation Technique for Constrained Forest Problems