×

Geometric partitioning and robust ad-hoc network design. (English) Zbl 1334.90065

Summary: We present fast approximation algorithms for the problem of dividing a given convex geographic region into smaller sub-regions so as to distribute the workloads of a set of vehicles. Our objective is to partition the region in such a fashion as to ensure that vehicles are capable of communicating with one another under limited communication radii. We consider variations of this problem in which sub-regions are constrained to have equal area or be convex, and as a side consequence, our approach yields a factor 1.99 approximation algorithm for the continuous \(k\)-centers problem on a convex polygon.

MSC:

90B80 Discrete location and assignment
90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alzoubi, K. M., Wan, P.-J., & Frieder, O. (2002) Message-optimal connected dominating sets in mobile ad hoc networks. In Proceedings of the 3rd ACM international symposium on mobile ad hoc networking and computing, (pp 157-164). · Zbl 1460.90028
[2] Aronov, B., Carmi, P., & Katz, M. J. (2009). Minimum-cost load-balancing partitions. Algorithmica, 54(3), 318-336. · Zbl 1191.68754 · doi:10.1007/s00453-007-9125-3
[3] Avis, D., & Toussaint, G. T. (1981). An efficient algorithm for decomposing a polygon into star-shaped polygons. Pattern Recognition, 13(6), 395-398. · doi:10.1016/0031-3203(81)90002-9
[4] Bereg, S., Bose, P., & Kirkpatrick, D. (2006). Equitable subdivisions within polygonal regions. Computational Geometry, 34(1), 20-27. · Zbl 1098.65023 · doi:10.1016/j.comgeo.2005.06.003
[5] Berman, O., Drezner, Z., Tamir, A., & Wesolowsky, G. O. (2009). Optimal location with equitable loads. Annals of Operations Research, 167(1), 307-325. · Zbl 1163.90591 · doi:10.1007/s10479-008-0339-9
[6] Brimberg, J., & Salhi, S. (2005). A continuous location-allocation problem with zone-dependent fixed cost. Annals of Operations Research, 136(1), 99-115. · Zbl 1114.90054 · doi:10.1007/s10479-005-2041-5
[7] Carlsson, J. G. (2012). Dividing a territory among several vehicles. INFORMS Journal on Computing, 24(4), 565-577. · Zbl 1460.90028 · doi:10.1287/ijoc.1110.0479
[8] Carlsson, J. G., Ge, D., Subramaniam, A., & Ye. Y. (2007). Solving the min-max multi-depot vehicle routing problem. In Proceedings of the FIELDS workshop on global optimization. · Zbl 1177.90035
[9] Haugland, D., Ho, S. C., & Laporte, G. (2007). Designing delivery districts for the vehicle routing problem with stochastic demands. European Journal of Operational Research, 180(3), 997-1010. · Zbl 1121.90021 · doi:10.1016/j.ejor.2005.11.070
[10] Hochbaum, D. S. (1997). Approximation algorithms for NP-hard problems, volume 20. PWS publishing company Boston. · Zbl 1368.68010
[11] Melissen, J. B. M., & Schuur, P. C. (2000). Covering a rectangle with six and seven circles. Discrete Applied Mathematics, 99(1), 149-156. · Zbl 0951.52017 · doi:10.1016/S0166-218X(99)00130-4
[12] Pavone, M., Arsie, A., Frazzoli, E., & Bullo, F. (2011). Distributed algorithms for environment partitioning in mobile robotic networks. Automatic Control, IEEE Transactions on, 56(8), 1834-1848. · Zbl 1368.93433 · doi:10.1109/TAC.2011.2112410
[13] Preparata, F. P., & Shamos, M. I. (1985). Computational geometry: An introduction. New York: Springer. · Zbl 0575.68059 · doi:10.1007/978-1-4612-1098-6
[14] Royer, E. M., Melliar-Smith, P. M., & Moser, L. E. (2001). An analysis of the optimum node density for ad hoc mobile networks. In IEEE International Conference on Communications, 2001. ICC 2001 (Vol. 3, pp. 857-861). · Zbl 1368.93433
[15] Stojmenovic, I. (2002). Position-based routing in ad hoc networks. IEEE Communications Magazine, 40(7), 128-134. · doi:10.1109/MCOM.2002.1018018
[16] Valiente, G. (2013). Algorithms on trees and graphs. Berlin: Springer. · Zbl 1007.05001
[17] Wattenhofer, R., Li, L., Bahl, P., & Wang, Y.-M. (2001) Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In INFOCOM 2001. Twentieth annual joint conference of the IEEE computer and communications societies. Proceedings. IEEE (Vol. 3, pp. 1388-1397)
[18] Wu J., & Li, H. (1999) On calculating connected dominating set for efficient routing in ad hoc wireless networks. In Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, (pp. 7-14).
[19] Youla, D. C., & Webb, H. (1982). Image restoration by the method of convex projections: Part 1: Theory. IEEE Transactions on Medical Imaging, 1(2), 81-94. · doi:10.1109/TMI.1982.4307555
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.