zbMATH — the first resource for mathematics

A PTAS for the weighted unit disk cover problem. (English) Zbl 1440.68335
Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 898-909 (2015).
Summary: We are given a set of weighted unit disks and a set of points in Euclidean plane. The minimum weight unit disk cover (WUDC) problem asks for a subset of disks of minimum total weight that covers all given points. WUDC is one of the geometric set cover problems, which have been studied extensively for the past two decades (for many different geometric range spaces, such as (unit) disks, halfspaces, rectangles, triangles). It is known that the unweighted WUDC problem is NP-hard and admits a polynomial-time approximation scheme (PTAS). For the weighted WUDC problem, several constant approximations have been developed. However, whether the problem admits a PTAS has been an open question. In this paper, we answer this question affirmatively by presenting the first PTAS for WUDC. Our result implies the first PTAS for the minimum weight dominating set problem in unit disk graphs. Combining with existing ideas, our result can also be used to obtain the first PTAS for the maxmimum lifetime coverage problem and an improved constant approximation ratio for the connected dominating set problem in unit disk graphs.
For the entire collection see [Zbl 1316.68014].

68W25 Approximation algorithms
05C62 Graph representations (geometric and intersection representations, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
90C27 Combinatorial optimization
Full Text: DOI
[1] Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: FOC, pp. 400-409. IEEE (2013)
[2] Ambühl, C., Erlebach, T., Mihalák, M., Nunkesser, M.: Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs. In: Díaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol. 4110, pp. 3-14. Springer, Heidelberg (2006) · Zbl 1148.05308 · doi:10.1007/11830924_3
[3] Bansal, N., Pruhs, K.: The geometry of scheduling. SICOMP 43(5), 1684-1698 (2014) · Zbl 1335.90031
[4] Brönnimann, H., Goodrich, M.: Almost optimal set covers in finite vc-dimension. DCG 14(1), 463-479 (1995) · Zbl 0841.68122
[5] Bus, N., Garg, S., Mustafa, N. H., Ray, S.: Tighter estimates for epsilon-nets for disks. arXiv preprint (2015). · Zbl 1334.65048
[6] Chan, T.M., Grant, E.: Exact algorithms and apx-hardness results for geometric packing and covering problems. In: CGTA 47, 2, Part A, pp. 112-124 (2014) · Zbl 1283.52032
[7] Chan, T. M., Grant, E., Könemann, J., Sharpe, M.: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In: SODA, pp. 1576-1585. SIAM (2012)
[8] Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1-3), 165-177 (1991) · Zbl 0739.05079
[9] Clarkson, K.L., Varadarajan, K.: Improved approximation algorithms for geometric set cover. DCG 37(1), 43-58 (2007) · Zbl 1106.68121
[10] Dai, D., Yu, C.: A · Zbl 1162.68042 · doi:10.1016/j.tcs.2008.11.015
[11] Ding, L., Wu, W., Willson, J., Wu, L., Lu, Z., Lee, W.: Constant-approximation for target coverage problem in wireless sensor networks. In: INFOCOM, pp. 1584-1592. IEEE (2012)
[12] Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: STOC, pp. 624-633. ACM (2014) · Zbl 1315.91001
[13] Du, D.-Z., Ko, K., Hu, X.: Design and Analysis of Approximation Algorithms. Springer (2011)
[14] Du, D.-Z., Wan, P.-J.: Connected Dominating Set: Theory and Applications, vol. 77. Springer Science & Business Media (2012)
[15] Erlebach, T., Grant, T., Kammer, F.: Maximising lifetime for fault-tolerant target coverage in sensor networks. In: SPAA, pp. 187-196. ACM (2011)
[16] Erlebach, T., Mihalák, M.: A (4 + · Zbl 1284.68663 · doi:10.1007/978-3-642-12450-1_13
[17] Erlebach, T., van Leeuwen, E.: Ptas for weighted set cover on unit squares. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX. LNCS, vol. 6302, pp. 166-177. Springer, Heidelberg (2010) · Zbl 1304.68214
[18] Even, G., Rawitz, D., Shahar, S.M.: Hitting sets when the vc-dimension is small. Information Processing Letters 95(2), 358-362 (2005) · Zbl 1184.68632 · doi:10.1016/j.ipl.2005.03.010
[19] Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM (JACM) 45(4), 634-652 (1998) · Zbl 1065.68573 · doi:10.1145/285055.285059
[20] Gibson, M., Pirwani, I.A.: Algorithms for dominating set in disk graphs: breaking the logn barrier. In: ESA, pp. 243-254. Springer (2010) · Zbl 1287.05149
[21] Har-Peled, S., Kaplan, H., Sharir, M., Smorodinsky, S.: Epsilon-nets for halfspaces revisited (2014). arXiv preprint
[22] Har-Peled, S., Lee, M.: Weighted geometric set cover problems revisited. JoCG 3(1), 65-85 (2012) · Zbl 1404.68192
[23] Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and vlsi. JACM 32(1), 130-136 (1985) · Zbl 0633.68027 · doi:10.1145/2455.214106
[24] Hochbaum, D.S., Maass, W.: Fast approximation algorithms for a nonconvex covering problem. Journal of Algorithms 8(3), 305-323 (1987) · Zbl 0636.68082 · doi:10.1016/0196-6774(87)90012-5
[25] Huang, Y., Gao, X., Zhang, Z., Wu, W.: A better constant-factor approximation for weighted dominating set in unit disk graph. JCO 18(2), 179-194 (2009) · Zbl 1184.05090
[26] Hunt, H.B., III, Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs (1997) · Zbl 0894.68105
[27] Marx, D.: On the optimality of planar and geometric approximation schemes. In: FOCS, pp. 338-348. IEEE (2007)
[28] Mustafa, N.H., Raman, R., Ray, S.: Qptas for geometric set-cover problems via optimal separators (2014). arXiv preprint
[29] Mustafa, N.H., Ray, S.: Ptas for geometric hitting set problems via local search. In: SOCG, pp. 17-22. ACM (2009) · Zbl 1380.68403
[30] Pyrga, E., Ray, S.: New existence proofs · Zbl 1221.52016
[31] van Leeuwen, E.J.: Optimization and approximation on systems of geometric objects. Phd thesis
[32] Varadarajan, K.: Epsilon nets and union complexity. In: SOCG, SCG 2009, pp. 11-16. ACM (2009) · Zbl 1380.68407
[33] Varadarajan, K.: Weighted geometric set cover via quasi-uniform sampling. In: SOCG, pp. 641-648. ACM (2010) · Zbl 1293.68300
[34] Zou, F., Wang, Y., Xu, X.-H., Li, X., Du, H., Wan, P., Wu, W.: New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. TCS 412(3), 198-208 (2011) · Zbl 1209.68389 · doi:10.1016/j.tcs.2009.06.022
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.