No Access

The Bursty Steiner Tree Problem

Gokarna Sharma

Department of Computer Science, Kent State University, Kent, OH 44242, USA

E-mail Address: sharma@cs.kent.edu

Search for more papers by this author

and

Costas Busch

School of Electrical Engineering and Computer Science, Louisiana State University, Baton Rouge, LA 70803, USA

E-mail Address: busch@csc.lsu.edu

Search for more papers by this author

https://doi.org/10.1142/S0129054117500290Cited by:0 (Source: Crossref)

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 $Θ (min {log k, m})$ $Θ (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 $α$ , we provide a competitive ratio for this problem with a gap of $𝒪 (min {α, m})$ factor between the lower bound and the upper bound. We also show that a tight bound of $Θ (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.

A preliminary version of this paper appeared in the Proceedings of CCCG’2014 [19] with title “A Note on Online Steiner Tree Problems.”

Communicated by Giorgio Ausiello

Keywords:

References

1. S. Angelopoulos, Improved bounds for the online Steiner tree problem in graphs of bounded edge-asymmetry. In SODA, pages 248–257, 2007. Google Scholar
2. S. Angelopoulos, A near-tight bound for the online Steiner tree problem in graphs of bounded asymmetry. In ESA, pages 76–87, 2008. Google Scholar
3. S. Angelopoulos, On the competitiveness of the online asymmetric and Euclidean Steiner tree problems. In WAOA, pages 1–12, 2010. Google Scholar
4. M. Bern and P. Plassmann, The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32(4) :171–176, 1989. Crossref, Web of Science, Google Scholar
5. J. Byrka, F. Grandoni, T. Rothvoss and L. Sanita, Steiner tree approximation via iterative randomized rounding. J. ACM 60(1) :6:1–6:33, 2013. Crossref, Web of Science, Google Scholar
6. Y. Chen, An improved approximation algorithm for the terminal Steiner tree problem. In ICCSA, pages 141–151, 2011. Google Scholar
7. M. Faloutsos, R. Pankaj and K. C. Sevcik, The effect of asymmetry on the on-line multicast routing problem. Int. J. Found. Comput. Sci. 13(6) :889–910, 2002. Link, Google Scholar
8. M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York, 1990). Google Scholar
9. N. Garg, G. Konjevod and R. Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms 37(1) :66–84, 2000. Crossref, Web of Science, Google Scholar
10. R. L. Graham, Bounds for certain multiprocessing anomalies. Bell System Technical Journal 45 :1563–1581, 1966. Crossref, Web of Science, Google Scholar
11. M. Imase and B. M. Waxman, Dynamic Steiner tree problem. SIAM J. Discrete Math. 4(3) :369–384, 1991. Crossref, Web of Science, Google Scholar
12. G.-H. Lin and G. Xue, On the terminal Steiner tree problem. Inf. Process. Lett. 84(2) :103–107, 2002. Crossref, Web of Science, Google Scholar
13. C. L. Lu, C. Y. Tang and R. C.-T. Lee, The full Steiner tree problem. Theoretical Computer Science 306(1–3) :55–67, 2003. Crossref, Web of Science, Google Scholar
14. R. Motwani, V. Saraswat and E. Torng, Online scheduling with lookahead: Multipass assembly lines. INFORMS J. on Computing 10(3) :331–340, Mar. 1998. Crossref, Google Scholar
15. J. S. Naor, D. Panigrahi and M. Singh, Online node-weighted Steiner tree and related problems. In FOCS, pages 210–219, 2011. Google Scholar
16. S. Ramanathan, Multicast tree generation in networks with asymmetric links. IEEE/ACM Trans. Netw. 4(4) :558–568, 1996. Crossref, Web of Science, Google Scholar
17. A. Segev, The node-weighted Steiner tree problem. Netw. 17(1) :1–17, 1987. Crossref, Web of Science, Google Scholar
18. G. Sharma and C. Busch, Near-optimal deterministic Steiner tree maintenance in sensor networks. In DCOSS, pages 201–208, 2014. Google Scholar
19. G. Sharma and C. Busch, A note on online Steiner tree problems. In CCCG, pages 107–112, 2014. Google Scholar
20. D. D. Sleator and R. E. Tarjan, Amortized efficiency of list update and paging rules. Commun. ACM 28(2) :202–208, 1985. Crossref, Web of Science, Google Scholar
21. H. Takahashi and A. Matsuyama, An approximate solution for the Steiner problem in graphs. Math. Japonica 24 :573–577, 1980. Google Scholar
22. J. Westbrook and D. C. K. Yan, Linear bounds for on-line Steiner problems. Inf. Process. Lett. 55(2) :59–63, 1995. Crossref, Web of Science, Google Scholar