IEICE TRANSACTIONS on Fundamentals
Efficient Algorithms for the Partial Sum Dispersion Problem
Summary :
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).
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.10 pp.1206-1210
- Publication Date
- 2020/10/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2019DMP0011
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- optimization
Authors
Toshihiro AKAGI
TOME R&D Inc
Tetsuya ARAKI
Gunma University
Shin-ichi NAKANO
Gunma University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
