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

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

0.00 Avg rating0 Votes
Article ID: iaor20083342
Country: Netherlands
Volume: 103
Issue: 5
Start Page Number: 195
End Page Number: 202
Publication Date: Aug 2007
Journal: Information Processing Letters
Authors: , , ,
Keywords: duality, orienteering
Abstract:

The primal–dual scheme has been used to provide approximation algorithms for many problems. Goemans and Williamson gave a (2-1/(n-1))-approximation for the Prize-Collecting Steiner Tree Problem that runs in O(n logn) time – it applies the primal–dual scheme once for each of the n vertices of the graph. We present a primal–dual algorithm that runs in O(n logn), as it applies this scheme only once, and achieves the slightly better ratio of (2-2/n). We also show a tight example for the analysis of the algorithm and discuss briefly a couple of other algorithms described in the literature.

Reviews

Required fields are marked *. Your email address will not be published.