Abstract
We consider the problem of Single-Tiered Relay Placement with Basestations, which takes as input a set \(S\) of sensors and a set \(B\) of basestations described as points in a normed space \((M,d)\), and real numbers \(0< r\le R\). The objective is to place a minimum cardinality set \(Q\) of wireless relay nodes that connects \(S\) and \(B\) according to the following rules. The sensors in \(S\) can communicate within distance \(r\), relay nodes in \(Q\) can communicate within distance \(R\), and basestations are considered to have an infinite broadcast range. Together the sets \(S, B\), and \(Q\) induce an undirected graph \(G=(V,E)\) defined as follows: \(V=S\cup B\cup Q\) and \(E=\{uv|u,v\in B\}\cup \{uv|u\in Q\) and \(v\in Q\cup B\) and \(d(u,v)\le R\} \cup \{uv|u\in S\) and \(v\in S\cup Q\cup B\) and \(d(u,v)\le r\}\). Then \(Q\) connects \(S\) and \(B\) when this induced graph is connected. In the case of the two-dimensional Euclidean plane, we get a \((1+\ln 6+\epsilon )<2.8\)-approximation algorithm, improving the previous best ratio of 3.11. Let \(\varDelta \) be the maximum number of points on a unit ball with pairwise distance strictly bigger than 1. Under certain assumptions, we have a \(\left( 1+\ln (\varDelta +1)+\epsilon \right) \)-approximation algorithm. When biconnectivity is required, we show that a variant of our previously proposed algorithm has approximation ratio of \(\varDelta + 2\). In the case of the two-dimensional Euclidean plane, our ratio of 7 improves our previous bound of 16.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arora S (1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. JACM 45(5):753–782
Auletta V, Dinitz Y, Nutov Z, Parente D (1999) A 2-approximation algorithm for finding an optimum 3-vertex-connected spanning subgraph. J Algorithms 32:21–30
Borchers A, Du D-Z (1997) The k-Steiner ratio in graphs. SIAM J Comput 26(3):857–869
Bryant V (1985) Metric spaces: iteration and application. Cambridge University Press, Cambridge
Calinescu G (2012) Relay placement for two-connectivity. In: Bestak R, Kencl L, Li LE, Widmer J, Yin H (eds) Networking (2) lecture notes in computer science, vol 7290. Springer, Berlin, pp 366–377
Calinescu G, Tongngam S (2008) Relay nodes in wireless sensor networks. In: Li Y, Huynh DT, Das S, Du D-Z (eds) Wireless algorithms, systems, and applications, of lecture notes in computer science, vol 5258. Springer, Berlin, pp 286–297
Chen D, Du D-Z, Hu X-D, Lin G-H, Wang L, Xue G (2001) Approximations for Steiner trees with minimum number of Steiner points. Theor Comput Sci 262(12):83–99
Cheng X, Du D-Z, Wang L, Xu B (2008) Relay sensor placement in wireless sensor networks. Wirel. Netw. 14(3):347–355
Cohen N, Nutov Z (2013) Approximating 0,1,2-survivable networks with minimum number of Steiner points. CoRR, arXiv:1304.7571
Efrat A, Fekete SP, Gaddehosur PR, Mitchell JS, Polishchuk V, Suomela J (2008) Improved approximation algorithms for relay placement. In: Halperin D, Mehlhorn K (eds) Algorithms - ESA 2008, lecture notes in computer science, vol 5193. Springer, Berlin / Heidelberg, pp 356–367
Efrat A, Fekete S.P, Gaddehosur P.R, Mitchell J.S, Polishchuk V, Suomela J Improved approximation algorithms for relay placement. from http://webstaff.itn.liu.se/valpo40/pages/papers.html
Fleischer L, Jain K, Williamson DP (2006) Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J Comput Syst Sci 72:838–867
Frank A (2011) Connections in combinatorial optimization. Oxford University Press, Oxford
Frank A, Tardos E (1989) An application of submodular flows. Linear Algebr Appl 114(115):320–348
Gabow HN (1993) A representation for crossing set families with applications to submodular flow problems. In: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, SODA ’93, pages 202–211, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics
Gröpl C, Hougardy S, Nierhoff T, Prömel HJ (2001) Approximation algorithms for the Steiner tree problem in graphs. In: Du D-Z, Cheng X (eds) Steiner trees in industries. Kluwer Academic Publishers, Dordrecht, pp 235–279
Kashyap A, Khuller S, Shayman M (2006) Relay placement for higher order connectivity in wireless sensor networks. INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, pp 1–12
Kashyap A, Khuller S, Shayman MA (2011) Relay placement for fault tolerance in wireless networks in higher dimensions. Comput Geom 44(4):206–215
Khuller S, Raghavachari B (1996) Improved approximation algorithms for uniform connectivity problems. J Algorithms 21:433–450
Lin G-H, Xue G (1999) Steiner tree problem with minimum number of Steiner points and bounded edge-length. Inf Process Lett 69(2):53–57
Lloyd EL, Xue G (2007) Relay node placement in wireless sensor networks. IEEE Trans Comput 56(1):134–138
Mandoiu II, Zelikovsky AZ (2000) A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points. Inf Process Lett 75(4):165–167
Martini H, Swanepoel KJ (2006) Low-degree minimal spanning trees in normed spaces. Appl Math Lett 19(2):122–125
Nutov Z, Yaroshevitch A (2009) Wireless network design via 3-decompositions. Inf Process Lett 109(19):1136–1140
Robins G, Salowe JS (1995) Low-degree minimum spanning trees. Discret Comput Geom 14(2):151–165
Tang J, Hao B, Sen A (2006) Relay node placement in large scale wireless sensor networks. Comput Commun 29:490–501
Zelikovsky A (1996) Better approximation bounds for the network and Euclidean Steiner tree problems. Technical Report CS-96-06, Department of Computer Science, University of Virginia
Zelikovsky AZ (1993) An 11/6-approximation algorithm for the network Steiner problem. Algorithmica 9(5):463–470
Zhang W, Xue G, Misra S (2007) Fault-tolerant relay node placement in wireless sensor networks: Problems and algorithms. INFOCOM 2007. Proceedings 26th IEEE International Conference on Computer Communications. pp 1649–1657
Acknowledgments
Gruia Calinescu research was supported in part by NSF Grant CCF-0515088. Benjamin Grimmer research was supported in part by a College of Science Undergraduate Summer Research Award. Satyajayant Misra research was done while at Arizona State University, and was supported in part by ARO Grant W911NF-04-1-0385, and NSF Grants CNS-1248109 and HRD-1345232. Sutep Tongngam research was done while at the Illinois Institute of Technology, and was supported in part by NSF Grant CCF-0515088. Guoliang Xue research was supported in part by NSF Grant CCF-1115129 and ARO Grant W911AF-09-1-0467. The information reported here does not reflect the position or the policy of the federal government. Weiyi Zhang research was done while at Arizona State University, and was supported in part by NSF Grant ANI-0312635.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Calinescu, G., Grimmer, B., Misra, S. et al. Improved approximation algorithms for single-tiered relay placement. J Comb Optim 31, 1280–1297 (2016). https://doi.org/10.1007/s10878-014-9823-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-014-9823-0