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