Online steiner tree with deletions

Anupam Gupta, Amit Kumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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(n 3/2) edge changes for the first n requests, and maintained a constant-competitive tree online. In this paper we improve on these results: We give an online algorithm that maintains a Steiner tree under only deletions: we start off with a set of vertices, and at each time one of the vertices is removed from this set-our Steiner tree no longer has to span this vertex. We give an algorithm that changes only a constant number of edges upon each request, and maintains a constant-competitive tree at all times. Our algorithm uses the primal- dual framework and a global charging argument to carefully make these constant number of changes. We also give an algorithm that maintains a Steiner tree in the fully-dynamic model (where each request either adds or deletes a vertex). Our algorithm for this setting makes a constant number of changes per request in an amortized sense.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PublisherAssociation for Computing Machinery
Number of pages13
ISBN (Print)9781611973389
StatePublished - 2014
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
Duration: Jan 5 2014Jan 7 2014

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Country/TerritoryUnited States
CityPortland, OR

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Online steiner tree with deletions'. Together they form a unique fingerprint.

Cite this