Elementary approximation algorithms for prize collecting Steiner tree problems
type: Item
instance of: scholarly article
title: Elementary approximation algorithms for prize collecting Steiner tree problems
zbMATH Open document ID: 1192.68901
author: Shai Gutner
published in: Information Processing Letters
publication date: 2010-04-19T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5694951
zbMATH Keywords: approximation algorithms
zbMATH Keywords: prize collecting Steiner tree problem
zbMATH Keywords: local ratio
zbMATH Keywords: primal-dual
MaRDI profile type: Publication
full work available at URL: j.ipl.2007.12.010
OpenAlex ID: W2055226597
cites work: When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
cites work: A unified approach to approximating resource allocation and scheduling
cites work: One for the price of two: a unified approach for approximating covering problems
cites work: On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
cites work: A note on the prize collecting traveling salesman problem
cites work: A General Approximation Technique for Constrained Forest Problems
cites work: Q2934710
cites work: The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
cites work: Network design for information networks
cites work: Q4952698
cites work: A group-strategyproof mechanism for Steiner forests
cites work: Q2934723
DOI: 10.1016/J.IPL.2007.12.010
description: scientific article; zbMATH DE number 5694951