A Note on Online Steiner Tree Problems
Gokarna Sharma, Costas Busch · 2015
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 prob-lem which becomes the well-known online Steiner tree problem if the number of nodes in each burst is exactly one and becomes the classical Steiner tree problem if all the nodes that need to be connected appear in a single burst. In undirected graphs, we provide a tight bound of Θ(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 asymme-try α, we provide a near tight competitive ratio for this problem. We also consider a bursty variation of the ter-minal Steiner tree problem and provide the upper bound of min{4ρ, 3λm} and the lower bound of min{ρ/2,m/4} on the competitive ratio in undirected complete graphs, where λ is the current best approximation for the termi-nal Steiner tree problem and ρ = 12 log k. These are the first such results which provide clear performance trade-offs for the novel Steiner tree problem variations that subsume both of their online and classical versions. 1