Primal-dual approximation algorithms for the prize-collecting Steiner tree problem

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

zbMATH Keywords

primal-dual methodapproximation algorithmsprize-collecting Steiner tree

Mathematics Subject Classification ID

Approximation algorithms (68W25)

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