The Bursty Steiner Tree Problem

We introduce and study a new Steiner tree problem variation called the bursty Steiner tree problem where new nodes arrive into bursts. This is an online problem which becomes the well-known online Steiner tree problem if the number of nodes in each burst is exactly one and becomes the classic Steiner tree problem if all the nodes appear in a single burst. In undirected graphs, we provide a tight bound of Theta(min{log k, m}) on the competitive ratio for this problem, where k is the total number of nodes to be connected and m is the total number of different bursts. In directed graphs of bounded edge asymmetry alpha, we provide a competitive ratio for this problem with a gap of O(min{alpha, m}) factor between the lower bound and the upper bound. We also show that a tight bound of Theta(min{log k, m}) on the competitive ratio can be obtained for a bursty variation of the terminal Steiner tree problem. These are the first results that provide clear performance trade-offs for a novel Steiner tree problem variation that subsumes both of its online and classic versions.