Abstract
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 θ(minflog k;mg) 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 α , we provide a competitive ratio for this problem with a gap of O(min{α;m}) factor between the lower bound and the upper bound. We also show that a tight bound of (minflog k;mg) 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.
Original language | English (US) |
---|---|
Pages (from-to) | 869-887 |
Number of pages | 19 |
Journal | International Journal of Foundations of Computer Science |
Volume | 28 |
Issue number | 7 |
DOIs | |
State | Published - Nov 1 2017 |
Externally published | Yes |
Keywords
- Approximation
- Online execution
- Steiner tree
- Terminal bursts
- Terminal steiner tree
ASJC Scopus subject areas
- Computer Science (miscellaneous)