Online node-weighted Steiner forest and extensions via disk paintings
Journal Article (Journal Article)
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.
Full Text
Duke Authors
Cited Authors
- Hajiaghayi, M; Liaghat, V; Panigrahi, D
Published Date
- January 1, 2017
Published In
Volume / Issue
- 46 / 3
Start / End Page
- 911 - 935
Electronic International Standard Serial Number (EISSN)
- 1095-7111
International Standard Serial Number (ISSN)
- 0097-5397
Digital Object Identifier (DOI)
- 10.1137/14098692X
Citation Source
- Scopus