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

Efficient Algorithms for the Partial Sum Dispersion Problem Algorithmes efficaces pour le problème de dispersion de somme partielle

Toshihiro AKAGI, Tetsuya ARAKI, Shin-ichi NAKANO

  • Vues en texte intégral

    0

  • Citer

Résumé:

Le problème de la dispersion est une variante du problème de localisation des installations. Étant donné un ensemble P of n des points et un entier k, nous avons l'intention de trouver un sous-ensemble S of P avec |S|=k tel que le coût minpS{sables moins coûteux(p)} est maximisé, où sables moins coûteux(p) est la somme des distances de p au plus proche c points dans S. Nous appelons ce problème le problème de dispersion avec c coût total, ou le problème de dispersion PcS. Dans cet article, nous présentons deux algorithmes pour résoudre le problème de dispersion P2S (c=2) si tous les points de P sont en ligne. Les temps d'exécution des algorithmes sont O(kn2 enregistrer n) et O(n enregistrer n), respectivement. Nous présentons également un algorithme pour résoudre le problème de dispersion PcS si tous les points de P sont en ligne. Le temps d’exécution de l’algorithme est O(knc+1).

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.10 pp.1206-1210
Date de publication
2020/10/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.2019DMP0011
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories
à mettre en œuvre pour gérer une entreprise rentable. Ce guide est basé sur trois décennies d'expérience

Auteurs

Toshihiro AKAGI
  TOME R&D Inc
Tetsuya ARAKI
  Gunma University
Shin-ichi NAKANO
  Gunma University

Mots-clés

Table des matières