Abstract
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.
Research supported in part by the National Basic Research Program of China Grant 2015CB358700, 2011CBA00300, 2011CBA00301, the National Natural Science Foundation of China Grant 61202009, 61033001, 61361136003.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: FOC, pp. 400–409. IEEE (2013)
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)
Bansal, N., Pruhs, K.: The geometry of scheduling. SICOMP 43(5), 1684–1698 (2014)
Brönnimann, H., Goodrich, M.: Almost optimal set covers in finite vc-dimension. DCG 14(1), 463–479 (1995)
Bus, N., Garg, S., Mustafa, N. H., Ray, S.: Tighter estimates for epsilon-nets for disks. arXiv preprint (2015). arXiv:1501.03246
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)
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)
Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1–3), 165–177 (1991)
Clarkson, K.L., Varadarajan, K.: Improved approximation algorithms for geometric set cover. DCG 37(1), 43–58 (2007)
Dai, D., Yu, C.: A \(5+\epsilon \)-approximation algorithm for minimum weighted dominating set in unit disk graph. TCS 410(8), 756–765 (2009)
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)
Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: STOC, pp. 624–633. ACM (2014)
Du, D.-Z., Ko, K., Hu, X.: Design and Analysis of Approximation Algorithms. Springer (2011)
Du, D.-Z., Wan, P.-J.: Connected Dominating Set: Theory and Applications, vol. 77. Springer Science & Business Media (2012)
Erlebach, T., Grant, T., Kammer, F.: Maximising lifetime for fault-tolerant target coverage in sensor networks. In: SPAA, pp. 187–196. ACM (2011)
Erlebach, T., Mihalák, M.: A (4 + \(\epsilon \))-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs. In: Bampis, E., Jansen, K. (eds.) WAOA 2009. LNCS, vol. 5893, pp. 135–146. Springer, Heidelberg (2010)
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)
Even, G., Rawitz, D., Shahar, S.M.: Hitting sets when the vc-dimension is small. Information Processing Letters 95(2), 358–362 (2005)
Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM (JACM) 45(4), 634–652 (1998)
Gibson, M., Pirwani, I.A.: Algorithms for dominating set in disk graphs: breaking the logn barrier. In: ESA, pp. 243–254. Springer (2010)
Har-Peled, S., Kaplan, H., Sharir, M., Smorodinsky, S.: Epsilon-nets for halfspaces revisited (2014). arXiv preprint arXiv:1410.3154
Har-Peled, S., Lee, M.: Weighted geometric set cover problems revisited. JoCG 3(1), 65–85 (2012)
Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and vlsi. JACM 32(1), 130–136 (1985)
Hochbaum, D.S., Maass, W.: Fast approximation algorithms for a nonconvex covering problem. Journal of Algorithms 8(3), 305–323 (1987)
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)
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)
Marx, D.: On the optimality of planar and geometric approximation schemes. In: FOCS, pp. 338–348. IEEE (2007)
Mustafa, N.H., Raman, R., Ray, S.: Qptas for geometric set-cover problems via optimal separators (2014). arXiv preprint arXiv:1403.0835
Mustafa, N.H., Ray, S.: Ptas for geometric hitting set problems via local search. In: SOCG, pp. 17–22. ACM (2009)
Pyrga, E., Ray, S.: New existence proofs \(\varepsilon \)-nets. In: SOCG, pp. 199–207. ACM (2008)
van Leeuwen, E.J.: Optimization and approximation on systems of geometric objects. Phd thesis
Varadarajan, K.: Epsilon nets and union complexity. In: SOCG, SCG 2009, pp. 11–16. ACM (2009)
Varadarajan, K.: Weighted geometric set cover via quasi-uniform sampling. In: SOCG, pp. 641–648. ACM (2010)
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)
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
Li, J., Jin, Y. (2015). A PTAS for the Weighted Unit Disk Cover Problem. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_73
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_73
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)