Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems

DOI10.1007/978-3-540-85097-7_23zbMath1168.90629OpenAlexW1513971048MaRDI QIDQ5505663

Shai Gutner

Publication date: 27 January 2009

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85097-7_23

zbMATH Keywords

approximation algorithmsprimal-duallocal ratioprize collecting Steiner tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (1)

Combinatorial optimization in system configuration design

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems