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
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 minp∈S{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).
Toshihiro AKAGI
TOME R&D Inc
Tetsuya ARAKI
Gunma University
Shin-ichi NAKANO
Gunma University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Toshihiro AKAGI, Tetsuya ARAKI, Shin-ichi NAKANO, "Efficient Algorithms for the Partial Sum Dispersion Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E103-A, no. 10, pp. 1206-1210, October 2020, doi: 10.1587/transfun.2019DMP0011.
Abstract: The dispersion problem is a variant of the facility location problem. Given a set P of n points and an integer k, we intend to find a subset S of P with |S|=k such that the cost minp∈S{cost(p)} is maximized, where cost(p) is the sum of the distances from p to the nearest c points in S. We call the problem the dispersion problem with partial c sum cost, or the PcS-dispersion problem. In this paper we present two algorithms to solve the P2S-dispersion problem(c=2) if all points of P are on a line. The running times of the algorithms are O(kn2 log n) and O(n log n), respectively. We also present an algorithm to solve the PcS-dispersion problem if all points of P are on a line. The running time of the algorithm is O(knc+1).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2019DMP0011/_p
Copier
@ARTICLE{e103-a_10_1206,
author={Toshihiro AKAGI, Tetsuya ARAKI, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Algorithms for the Partial Sum Dispersion Problem},
year={2020},
volume={E103-A},
number={10},
pages={1206-1210},
abstract={The dispersion problem is a variant of the facility location problem. Given a set P of n points and an integer k, we intend to find a subset S of P with |S|=k such that the cost minp∈S{cost(p)} is maximized, where cost(p) is the sum of the distances from p to the nearest c points in S. We call the problem the dispersion problem with partial c sum cost, or the PcS-dispersion problem. In this paper we present two algorithms to solve the P2S-dispersion problem(c=2) if all points of P are on a line. The running times of the algorithms are O(kn2 log n) and O(n log n), respectively. We also present an algorithm to solve the PcS-dispersion problem if all points of P are on a line. The running time of the algorithm is O(knc+1).},
keywords={},
doi={10.1587/transfun.2019DMP0011},
ISSN={1745-1337},
month={October},}
Copier
TY - JOUR
TI - Efficient Algorithms for the Partial Sum Dispersion Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1206
EP - 1210
AU - Toshihiro AKAGI
AU - Tetsuya ARAKI
AU - Shin-ichi NAKANO
PY - 2020
DO - 10.1587/transfun.2019DMP0011
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E103-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2020
AB - The dispersion problem is a variant of the facility location problem. Given a set P of n points and an integer k, we intend to find a subset S of P with |S|=k such that the cost minp∈S{cost(p)} is maximized, where cost(p) is the sum of the distances from p to the nearest c points in S. We call the problem the dispersion problem with partial c sum cost, or the PcS-dispersion problem. In this paper we present two algorithms to solve the P2S-dispersion problem(c=2) if all points of P are on a line. The running times of the algorithms are O(kn2 log n) and O(n log n), respectively. We also present an algorithm to solve the PcS-dispersion problem if all points of P are on a line. The running time of the algorithm is O(knc+1).
ER -