Elementary approximation algorithms for prize collecting Steiner tree problems

DOI10.1016/j.ipl.2007.12.010zbMath1192.68901OpenAlexW2055226597MaRDI QIDQ963393

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

zbMATH Keywords

approximation algorithmsprimal-duallocal ratioprize collecting Steiner tree problem

Mathematics Subject Classification ID

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 note on the prize collecting traveling salesman problem
• 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 General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
• A unified approach to approximating resource allocation and scheduling
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Elementary approximation algorithms for prize collecting Steiner tree problems