Skip to main content

2019 | OriginalPaper | Buchkapitel

Capacitated Discrete Unit Disk Cover

verfasst von : Pawan K. Mishra, Sangram K. Jena, Gautam K. Das, S. V. Rao

Erschienen in: WALCOM: Algorithms and Computation

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Consider a capacitated version of the discrete unit disk cover problem as follows: consider a set \(P= \{p_1,p_2, \cdots ,p_n\}\) of n customers and a set \(Q=\{q_1,q_2, \cdots ,q_m\}\) of m service centers. A service center can provide service to at most \(\alpha ( \in \mathbb {N})\) number of customers. Each \(q_i \in Q\) \((i=1,2, \cdots ,m)\) has a preassigned set of customers to which it can provide service. The objective of the capacitated covering problem is to provide service to each customer in P by at least one service center in Q. In this paper, we consider the geometric version of the capacitated covering problem, where the set of customers and set of service centers are two point sets in the Euclidean plane. A service center can provide service to a customer if their Euclidean distance is less than or equal to 1. We call this problem as \((\alpha , P, Q)\)-covering problem. For the \((\alpha , P, Q)\)-covering problem, we propose an \(O(\alpha mn(m+n))\) time algorithm to check feasible solution for a given instance. We also prove that the \((\alpha , P, Q)\)-covering problem is NP-complete for \(\alpha \ge 3\) and it admits a PTAS.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat 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/RANDOM -2006. LNCS, vol. 4110, pp. 3–14. Springer, Heidelberg (2006). https://doi.org/10.1007/11830924_3CrossRefMATH 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/RANDOM -2006. LNCS, vol. 4110, pp. 3–14. Springer, Heidelberg (2006). https://​doi.​org/​10.​1007/​11830924_​3CrossRefMATH
2.
Zurück zum Zitat Basappa, M., Acharyya, R., Das, G.K.: Unit disk cover problem in 2D. J. Discrete Algorithms 33, 193–201 (2015)MathSciNetCrossRef Basappa, M., Acharyya, R., Das, G.K.: Unit disk cover problem in 2D. J. Discrete Algorithms 33, 193–201 (2015)MathSciNetCrossRef
3.
4.
Zurück zum Zitat Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463–479 (1995)MathSciNetCrossRef Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463–479 (1995)MathSciNetCrossRef
5.
Zurück zum Zitat Călinescu, G., Mandoiu, I.I., Wan, P.J., Zelikovsky, A.Z.: Selecting forwarding neighbors in wireless ad hoc networks. Mobile Netw. Appl. 9(2), 101–111 (2004)CrossRef Călinescu, G., Mandoiu, I.I., Wan, P.J., Zelikovsky, A.Z.: Selecting forwarding neighbors in wireless ad hoc networks. Mobile Netw. Appl. 9(2), 101–111 (2004)CrossRef
7.
Zurück zum Zitat Claude, F., et al.: An improved line-separable algorithm for discrete unit disk cover. Discrete Math. Algorithms Appl. 2(01), 77–87 (2010)MathSciNetCrossRef Claude, F., et al.: An improved line-separable algorithm for discrete unit disk cover. Discrete Math. Algorithms Appl. 2(01), 77–87 (2010)MathSciNetCrossRef
8.
Zurück zum Zitat Das, G.K., Fraser, R., López-Ortiz, A., Nickerson, B.G.: On the discrete unit disk cover problem. Int. J. Comput. Geom. Appl. 22(05), 407–419 (2012)MathSciNetCrossRef Das, G.K., Fraser, R., López-Ortiz, A., Nickerson, B.G.: On the discrete unit disk cover problem. Int. J. Comput. Geom. Appl. 22(05), 407–419 (2012)MathSciNetCrossRef
9.
Zurück zum Zitat Federickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004–1022 (1987)MathSciNetCrossRef Federickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004–1022 (1987)MathSciNetCrossRef
10.
Zurück zum Zitat Feige, U.: A threshold of ln n for approximating set cover. J. ACM (JACM) 45(4), 634–652 (1998)CrossRef Feige, U.: A threshold of ln n for approximating set cover. J. ACM (JACM) 45(4), 634–652 (1998)CrossRef
11.
Zurück zum Zitat Fraser, R., López-Ortiz, A.: The within-strip discrete unit disk cover problem. Theor. Comput. Sci. 674, 99–115 (2017)MathSciNetCrossRef Fraser, R., López-Ortiz, A.: The within-strip discrete unit disk cover problem. Theor. Comput. Sci. 674, 99–115 (2017)MathSciNetCrossRef
12.
Zurück zum Zitat Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)MATH Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)MATH
13.
Zurück zum Zitat Haussler, D., Welzl, E.: \(\epsilon \)-nets and simplex range queries. Discrete & Computational Geometry 2(2), 127–151 (1987)MathSciNetCrossRef Haussler, D., Welzl, E.: \(\epsilon \)-nets and simplex range queries. Discrete & Computational Geometry 2(2), 127–151 (1987)MathSciNetCrossRef
14.
Zurück zum Zitat Kleinberg, J., Tardos, E.: Algorithm Design. Addison-Wesley Longman Publishing Co. Inc, Boston (2005) Kleinberg, J., Tardos, E.: Algorithm Design. Addison-Wesley Longman Publishing Co. Inc, Boston (2005)
15.
Zurück zum Zitat Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete Comput. Geom. 44(4), 883–895 (2010)MathSciNetCrossRef Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete Comput. Geom. 44(4), 883–895 (2010)MathSciNetCrossRef
16.
Zurück zum Zitat Mustafa, N.H., Ray, S.: PTAS for geometric hitting set problems via local search. In: Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry, pp. 17–22. ACM (2009) Mustafa, N.H., Ray, S.: PTAS for geometric hitting set problems via local search. In: Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry, pp. 17–22. ACM (2009)
17.
Metadaten
Titel
Capacitated Discrete Unit Disk Cover
verfasst von
Pawan K. Mishra
Sangram K. Jena
Gautam K. Das
S. V. Rao
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-10564-8_32