Online Steiner Tree with Deletions

Abstract

In the online Steiner tree problem, the input is a set of vertices that appear one-by-one, and we have to maintain a Steiner tree on the current set of vertices. The cost of the tree is the total length of edges in the tree, and we want this cost to be close to the cost of the optimal Steiner tree at all points in time. If we are allowed to only add edges, a tight bound of Θ(log n) on the competitiveness has been known for two decades. Recently it was shown that if we can add one new edge and make one edge swap upon every vertex arrival, we can still maintain a constant-competitive tree online. But what if the set of vertices sees both additions and deletions? Again, we would like to obtain a low-cost Steiner tree with as few edge changes as possible. The original paper of Imase and Waxman (SIAM J. Disc. Math, 4(3):369–384, 1991) had also considered this model, and it gave an algorithm that made at most O(n3/2) edge changes for the first n requests, and maintained a constant-competitive tree online. In this paper we improve on these results: