Paper Info
Title
An O(log n)-competitive algorithm for online constrained forest problems
Abstract
In the generalized Steiner tree problem, we find a minimumcost set of edges to connect a given set of source-sink pairs. In the online version of this problem, the source-sink pairs arrive over time. Agrawal, Klein, and Ravi give a 2-approximation algorithm for the offline problem; Berman and Coulston give an O(log n)-competitive algorithm for the online problem. Goemans and Williamson subsequently generalized the offline algorithm of Agrawal et al. to handle a large class of problems they called constrained forest problems, and other problems, such as the prize-collecting Steiner tree problem. In this paper, we show how to combine the ideas of Goemans and Williamson and those of Berman and Coulston to give an O(log n)-competitive algorithm for online constrained forest problems, including an online version of the prize-collecting Steiner tree problem.
Year
DOI
Venue
2011
10.1007/978-3-642-22006-7_4
ICALP
Keywords
DocType
Volume
forest problem,prize-collecting Steiner tree problem,competitive algorithm,online version,log n,source-sink pair,generalized Steiner tree problem,offline problem,online problem,2-approximation algorithm
Conference
6755
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Jiawei Qianand1291.82
David P. Williamson23564413.34