Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Journal of Combinatorial Optimization
Erschienen in: Journal of Combinatorial Optimization 3/2014

01.04.2014

An approximation algorithm for k-center problem on a convex polygon

verfasst von: Hai Du, Yinfeng Xu

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2014

Einloggen

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

search-config
loading …

Abstract

This paper studies the constrained version of the k-center location problem. Given a convex polygonal region, every point in the region originates a service demand. Our objective is to place k facilities lying on the region’s boundary, such that every point in that region receives service from its closest facility and the maximum service distance is minimized. This problem is equivalent to covering the polygon by k circles with centers on its boundary which have the smallest possible radius. We present an 1.8841-approximation polynomial time algorithm for this problem.
Vorheriger Artikel On the approximability of positive influence dominating set in social networks
Nächster Artikel Improved upper bound for acyclic chromatic index of planar graphs without 4-cycles

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
Literatur
Agarwal PK, Guibas LJ, Saxe J, Shor PW (1987) A linear time algorithms for computing the Voronoi diagram of a convex polygon. In: Proceedings of the 19th annual ACM symposium on theory of computing, pp 39–45
Agarwal PK, Sharir M, Toledo S (1994) Applications of parametric searching in geometric optimization. J Algorithms 17:292–318 CrossRefMathSciNet
Agarwal PK, Sharir M (1998) Efficient algorithms for geometric optimization. ACM Comput Surv 30:412–458 CrossRef
Bose P, Toussaint G (1996) Computing the constrained Euclidean, geodesic and link center of a simple polygon with applications. In: Proc of pacific graphics international, pp 102–112
Brass P, Knauer C, Na HS, Shin CS (2009) Computing k-centers on a line. CoRR abs/0902.​3282
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–427 CrossRefMATHMathSciNet
Hurtado F, Sacriscan V, Toussaint G (2000) Facility location problems with constraints. Stud Locat Anal 15:17–35 MATH
Kim SK, Shin CS (2000) Efficient algorithm for two-center problems for a convex polygon. In: Proceedings of the 6th international computing and combinatorics conference, Ban, NY, pp 299–309 CrossRef
Roy S, Bardhan D, Das S (2008) Base station placement on boundary of a convex polygon. J Parallel Distrib Comput 68:265–273 CrossRefMATH
Suzuki A, Drezner Z (1996) The p-center location problem in area. Location Sci 4:69–82 CrossRefMATH
Metadaten
Titel
An approximation algorithm for k-center problem on a convex polygon
verfasst von
Hai Du
Yinfeng Xu
Publikationsdatum
01.04.2014
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 3/2014
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-012-9532-5

Weitere Artikel der Ausgabe 3/2014

Journal of Combinatorial Optimization 3/2014 Zur Ausgabe

OriginalPaper

A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties

OriginalPaper

The Pfaffian property of Cartesian products of graphs

OriginalPaper

On the approximability of positive influence dominating set in social networks

OriginalPaper

On the performance of Scatter Search for post-enrolment course timetabling problems

OriginalPaper

Order consolidation for hierarchical product lines

OriginalPaper

Popularity at minimum cost