nach oben

Journal of Combinatorial Optimization

Erschienen in:

27.10.2017

The connected disk covering problem

verfasst von: Yi Xu, Jigen Peng, Wencheng Wang, Binhai Zhu

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2018

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Let P be a convex polygon with n vertices. We consider a variation of the K-center problem called the connected disk covering problem (CDCP), i.e., finding K congruent disks centered in P whose union covers P with the smallest possible radius, while a connected graph is generated by the centers of the K disks whose edge length can not exceed the radius. We give a 2.81-approximation algorithm in O(Kn) time.

Vorheriger Artikel Online lazy bureaucrat scheduling with a machine deadline

Nächster Artikel List-edge-coloring of planar graphs without 6-cycles with three chords

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Brass P, Knauer C, Na HS, Shin CS (2009) Computing k-centers on a line. arXiv preprint arXiv: 0902.3282

Clark BN, Colbourn CJ, Johnson DS (1990) Unit disk graphs. Discrete Math 86:165–177MathSciNetCrossRefMATH

Das GK, Das S, Nandy SC, Sinha BP (2006) Efficient algorithm for placing a given number of base stations to cover a convex region. J Parallel Distrib Comput 66(11):1353–1358CrossRefMATH

Das GK, Roy S, Das S, Nandy SC (2008) Variations of base station placement problem on the boundary of a convex region. Int J Found Comput Sci 19(2):405–427MathSciNetCrossRefMATH

Drezener Z (1984) The P-center problem. Heuristics and optimal algorithms. J Oper Res Soc 35:741–748

Du H, Xu YF (2014) An approximation algorithm for k-center problem on a convex polygon. J Comb Optim 27(3):504–518MathSciNetCrossRefMATH

Feder T, Greene D (1988) Optimal algorithms for approximate clustering. In: Proceedings of the 20th ACM symposium on theory of computing, pp 434–444

Gonzalez TF (1985) Clustering to minimize the maximum intercluster distance. Theor Comput Sci 38:293–306MathSciNetCrossRefMATH

Hochbaum DS, Shmoys DB (1985) A best possible heuristic for the k-center problem. Math Oper Res 10(2):180–184MathSciNetCrossRefMATH

Huang JH, Wang HL, Chao KM (2016) Computing the line-constrained k-center in the plane for small k. In: Algorithmic aspects in information and management. Springer International Publishing, pp 197–208

Hwang RZ, Lee RCT, Chang RC (1993) The slab dividing approach to solve the euclidean P-center problem. Algorithmica 9:1–22MathSciNetCrossRefMATH

Karmakar A, Das S, Nandy SC, Bhattacharya BK (2013) Some variations on constrained minimum enclosing circle problem. J Comb Optim 25(2):176–190MathSciNetCrossRefMATH

Megiddo N (1983) Linear-time algorithms for the linear programming in \(R^3\) and related problems. SIAM J Comput 12:759–776MathSciNetCrossRefMATH

Megiddo N, Supowit K (1984) On the complexity of some common geometric location problems. SIAM J Comput 13:1182–1196MathSciNetCrossRefMATH

Nurmela KJ, Ostergard PRJ (2000) Covering a square with up to 30 equal circles. Research Report HUT-TCS-A62, Laboratory for Theoretical Computer Science, Helsinky University of Technology

Rezaei M, FazelZarandi MH (2011) Facility location via fuzzy modeling and simulation. Appl Soft Comput 11:5330–5340CrossRef

Salhieh A, Weinmann J, Kochha M, Schwiebert L (2001) Power efficient topologies for wireless sensor networks. In: ICPP’2001, pp 156–163

Wu WL, Du HW, Jia XH, Li YS, Huang SCH (2006) Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theor Comput Sci 352:1–7MathSciNetCrossRefMATH

Titel: The connected disk covering problem
verfasst von: Yi Xu
Jigen Peng
Wencheng Wang
Binhai Zhu
Publikationsdatum: 27.10.2017
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2018
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-017-0195-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2018

The longest commonly positioned increasing subsequences problem

A low complexity semidefinite relaxation for large-scale MIMO detection

Online lazy bureaucrat scheduling with a machine deadline

List-edge-coloring of planar graphs without 6-cycles with three chords

Upper bounds for adjacent vertex-distinguishing edge coloring

Two-step values for games with two-level communication structure