Minimizing the maximum moving cost of interval coverages. (English) Zbl 1423.68550
Summary: In this paper, we consider an interval coverage problem. Given are \(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, where \(B\) is the barrier and each interval is the covering interval of a mobile sensor.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68W40 | Analysis of algorithms |
References:
| [1] | Andrews, A. M. and Wang, H., Minimizing the aggregate movements for interval coverage, Proc. \(1 4\) th Algorithms and Data Structures Symp. (WADS) (2015), pp. 28-39. · Zbl 1359.68279 |
| [2] | Bar-Noy, A. and Baumer, B., Average case network lifetime on an interval with adjustable sensing ranges, Algorithmica72 (2015) 148-166. · Zbl 1312.68025 |
| [3] | Bar-Noy, A., Rawitz, D. and Terlecky, P., Maximizing barrier coverage lifetime with mobile sensors, Proc. \(2 1\) st European Symp. Algorithms (ESA) (2013), pp. 97-108. · Zbl 1394.68009 |
| [4] | Chen, D. Z., Gu, Y., Li, J. and Wang, H., Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain, Discr. Comput. Geom.50 (2013) 374-408. · Zbl 1298.68276 |
| [5] | Cole, R., Salowe, J., Steiger, W. and Szemerédi, E., An optimal-time algorithm for slope selection, SIAM J. Comput.18(4) (1989) 792-810. · Zbl 0678.68033 |
| [6] | Cormen, T., Leiserson, C., Rivest, R. and Stein, C., Introduction to Algorithms, 3rd edn. (MIT Press, 2009). · Zbl 1187.68679 |
| [7] | Czyzowicz, J., Kranakis, E., Krizanc, D., Lambadaris, I., Narayanan, L., Opatrny, J., Stacho, L., Urrutia, J. and Yazdani, M., On minimizing the maximum sensor movement for barrier coverage of a line segment, Proc. 8th Int. Conf. Ad-Hoc, Mobile and Wireless Networks (2009), pp. 194-212. |
| [8] | Czyzowicz, J., Kranakis, E., Krizanc, D., Lambadaris, I., Narayanan, L., Opatrny, J., Stacho, L., Urrutia, J. and Yazdani, M., On minimizing the sum of sensor movements for barrier coverage of a line segment, Proc. \(9\) th Int. Conf. Ad-Hoc, Mobile and Wireless Networks (2010), pp. 29-42. |
| [9] | de Berg, M., Cheong, O., van Kreveld, M. and Overmars, M., Computational Geometry — Algorithms and Applications, 3rd edn. (Springer-Verlag, Berlin, 2008). · Zbl 1140.68069 |
| [10] | Fan, H., Li, M., Sun, X., Wan, P. and Zhao, Y., Barrier coverage by sensors with adjustable ranges, ACM Trans. Sensor Networks11 (2014) 14. |
| [11] | Kumar, S., Lai, T. H. and Arora, A., Barrier coverage with wireless sensors, Proc. \(1 1\) th Annual Int. Conf. Mobile Computing and Networking (MobiCom) (2005), pp. 284-298. |
| [12] | Megiddo, N., Applying parallel computation algorithms in the design of serial algorithms, J. ACM30(4) (1983) 852-865. · Zbl 0627.68034 |
| [13] | M. Mehrandish, On routing, backbone formation and barrier coverage in wireless ad doc and sensor networks, PhD thesis, Concordia University, Montreal, Quebec, Canada (2011). |
| [14] | Mehrandish, M., Narayanan, L. and Opatrny, J., Minimizing the number of sensors moved on line barriers, Proc. IEEE Wireless Communications and Networking Conf. (WCNC) (2011), pp. 653-658. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
