La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

An Approximation Algorithm for the 2-Dispersion Problem Un algorithme d'approximation pour le problème des 2 dispersions

Kazuyuki AMANO, Shin-ichi NAKANO

  • Vues en texte intégral

    0

  • Citer

Résumé:

Laisser nous P être un ensemble de points sur le plan, et d(p, q) soit la distance entre deux points p, q in P. Pour un point pP et un sous-ensemble S⊂P avec |S|≥3, le coût de 2-dispersion, noté sables moins coûteux2(p, S), de p par rapport à S est la somme de (1) la distance de p au point le plus proche dans Ssetmoins{p} et (2) la distance de p au deuxième point le plus proche dans Ssetmoins{p}. Le coût en 2 dispersions sables moins coûteux2(S) de S⊂P avec |S|≥3 est minp∈S{sables moins coûteux2(p, S)}. Étant donné un ensemble P of n des points et un entier k nous souhaitons calculer k sous-ensemble de points S of P avec maximum sables moins coûteux2(S). Dans cet article, nous donnons un simple algorithme d'approximation 1/({4sqrt{3}}) pour le problème.

Publication
IEICE TRANSACTIONS on Information Vol.E103-D No.3 pp.506-508
Date de publication
2020/03/01
Publicisé
2019/11/28
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2019FCP0005
Type de manuscrit
Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
Catégories

Auteurs

Kazuyuki AMANO
  Gunma University
Shin-ichi NAKANO
  Gunma University

Mots-clés

Table des matières