Online node-weighted Steiner forest and extensions via disk paintings
We give the first polynomial-time online algorithm for the node-weighted Steiner forest problem with a poly-logarithmic competitive ratio. The competitive ratio of our algorithm is optimal up to a logarithmic factor. For the special case of graphs with an excluded fixed minor (e.g., planar graphs), we obtain a logarithmic competitive ratio, which is optimal up to a constant, using a different online algorithm. Both these results are obtained as special cases of generic results for a large class of problems that can be encoded as online f0; 1g-proper functions. Our results are obtained by using a new framework for online network design problems that we call disk paintings. The central idea in this technique is to amortize the cost of primal updates to a set of carefully selected mutually disjoint fixed-radius dual disks centered at a subset of terminals. We hope that this framework will be useful for other online network design problems.
Hajiaghayi, M; Liaghat, V; Panigrahi, D
Volume / Issue
Start / End Page
Electronic International Standard Serial Number (EISSN)
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)