Online Node-Weighted Steiner Tree and Related Problems

We obtain the first online algorithms for the node-weighted Steiner tree, Steiner forest and group Steiner tree problems that achieve a poly-logarithmic competitive ratio. Our algorithm for the Steiner tree problem runs in polynomial time, while those for the other two problems take quasi-polynomial time. Our algorithms can be viewed as online LP rounding algorithms in the framework of Buchbinder and Naor (Foundations and Trends in Theoretical Computer Science, 2009); however, while the natural LP formulation of these problems do lead to fractional algorithms with a poly-logarithmic competitive ratio, we are unable to round these LPs online without losing a polynomial factor. Therefore, we design new LP formulations for these problems drawing on a combination of paradigms such as spider decompositions, low-depth Steiner trees, generalized group Steiner problems, etc. and use the additional structure provided by these to round the more sophisticated LPs losing only a poly-logarithmic factor in the competitive ratio. As further applications of our techniques, we also design polynomial-time online algorithms with poly-logarithmic competitive ratios for two fundamental network design problems in edge-weighted graphs: the group Steiner forest problem (thereby resolving an open question raised by Chekuri et. al. (SODA 2008)) and the single source ℓ-vertex connectivity problem (which complements similar results for the corresponding edge-connectivity problem due to Gupta et. al. (STOC 2009)).

Authors

• Joseph Naor
• Debmalya Panigrahi
• Mohit Singh

Keywords

• Steiner trees
• Algorithm design and analysis
• Vegetation
• Greedy algorithms
• Approximation algorithms
• Approximation methods
• Polynomials
• Steiner Tree
• Nodes In The Graph
• Algorithm For Problem
• Polynomial-time Algorithm
• Algorithmic Framework
• Online Algorithm
• Graph Problems
• Network Design Problem
• Theoretical Computer Science
• Competitive Ratio
• Undirected
• Linear Programming
• Set Of Covariates
• High Connectivity
• Tree Height
• Subtree
• Version Of Problem
• Pair Of Vertices
• Node Weights
• Set Cover Problem
• Facility Location Problem
• Competitive Algorithm
• Path In Order
• Terminal Pair
• Fractional Solution
• Coverage Problem
• Primal-dual Algorithm
• Integer Solution
• Connection Cost
• Survivable Network Design