Abstract
In this paper, we study an interval coverage problem. We are given n intervals of the same length on a line L and a line segment B on L. Each interval has a nonnegative weight. The goal is to move the intervals along L such that every point of B is covered by at least one interval and the maximum moving cost of all intervals is minimized, where the moving cost of each interval is its moving distance times its weight. Algorithms for the “unweighted” version of this problem have been given before. In this paper, we present a first-known algorithm for this weighted version and our algorithm runs in \(O(n^2\log n\log \log n)\) time. The problem has applications in mobile sensor barrier coverage.
H. Wang was supported in part by NSF under Grant CCF-1317143. Part of the work by X. Zhang was carried out during his visit at Utah State University.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
It might be more natural to pick the rightmost sensor of \(S_{i1}\) as \(s_{g(i)}\). In fact, an arbitrary one is sufficient.
References
Andrews, A.M., Wang, H.: Minimizing the aggregate movements for interval coverage. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 28–39. Springer, Heidelberg (2015)
Bar-Noy, A., Baumer, B.: Average case network lifetime on an interval with adjustable sensing ranges. Algorithmica 72, 148–166 (2015)
Bar-Noy, A., Rawitz, D., Terlecky, P.: Maximizing barrier coverage lifetime with mobile sensors. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 97–108. Springer, Heidelberg (2013)
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry – Algorithms and Applications, 3rd edn. Springer-Verlag, Berlin (2008)
Chen, D., Gu, Y., Li, J., Wang, H.: Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain. Discrete Comput. Geom. 50, 374–408 (2013)
Cole, R., Salowe, J., Steiger, W., Szemerédi, E.: An optimal-time algorithm for slope selection. SIAM J. Comput. 18(4), 792–810 (1989)
Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)
Czyzowicz, J., Kranakis, E., Krizanc, D., Lambadaris, I., Narayanan, L., Opatrny, J., Stacho, L., Urrutia, J., Yazdani, M.: On minimizing the maximum sensor movement for barrier coverage of a line segment. In: Ruiz, P.M., Garcia-Luna-Aceves, J.J. (eds.) ADHOC-NOW 2009. LNCS, vol. 5793, pp. 194–212. Springer, Heidelberg (2009)
Czyzowicz, J., Kranakis, E., Krizanc, D., Lambadaris, I., Narayanan, L., Opatrny, J., Stacho, L., Urrutia, J., Yazdani, M.: On minimizing the sum of sensor movements for barrier coverage of a line segment. In: Nikolaidis, I., Wu, K. (eds.) ADHOC-NOW 2010. LNCS, vol. 6288, pp. 29–42. Springer, Heidelberg (2010)
Fan, H., Li, M., Sun, X., Wan, P., Zhao, Y.: Barrier coverage by sensors with adjustable ranges. ACM Trans. Sens. Netw. 11, 14 (2014)
Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. J. ACM 30(4), 852–865 (1983)
Mehrandish, M.: On routing, backbone formation and barrier coverage in wireless Ad Hoc and sensor networks. Ph.D. thesis, Concordia University, Montreal, Quebec, Canada (2011)
Mehrandish, M., Narayanan, L., Opatrny, J.: Minimizing the number of sensors moved on line barriers. In: Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), pp. 653–658 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, H., Zhang, X. (2015). Minimizing the Maximum Moving Cost of Interval Coverage. In: Elbassioni, K., Makino, K. (eds) Algorithms and Computation. ISAAC 2015. Lecture Notes in Computer Science(), vol 9472. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48971-0_17
Download citation
DOI: https://doi.org/10.1007/978-3-662-48971-0_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48970-3
Online ISBN: 978-3-662-48971-0
eBook Packages: Computer ScienceComputer Science (R0)