A 2-approximation for the \(k\)-prize-collecting Steiner tree problem

DOI10.1007/s00453-021-00919-3OpenAlexW4225489905MaRDI QIDQ5970779

Lehilton L. C. Pedrosa, Hugo K. K. Rosado

Publication date: 8 December 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00919-3

zbMATH Keywords

approximation algorithmprimal-dual\(k\)-MSTprize-collecting Steiner tree\(k\)-prize-collecting Steiner tree

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• A 2.5-factor approximation algorithm for the \(k\)-MST problem
• A note on the prize collecting traveling salesman problem
• A constant-factor approximation algorithm for the \(k\)-MST problem
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
• The Design of Approximation Algorithms
• Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
• Saving an epsilon
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• A General Approximation Technique for Constrained Forest Problems
• Spanning Trees—Short or Small
• Steiner Tree Approximation via Iterative Randomized Rounding

This page was built for publication: A 2-approximation for the \(k\)-prize-collecting Steiner tree problem