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
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 p∈P 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.
Kazuyuki AMANO
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
Kazuyuki AMANO, Shin-ichi NAKANO, "An Approximation Algorithm for the 2-Dispersion Problem" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 3, pp. 506-508, March 2020, doi: 10.1587/transinf.2019FCP0005.
Abstract: Let P be a set of points on the plane, and d(p, q) be the distance between a pair of points p, q in P. For a point p∈P and a subset S ⊂ P with |S|≥3, the 2-dispersion cost, denoted by cost2(p, S), of p with respect to S is the sum of (1) the distance from p to the nearest point in Ssetminus{p} and (2) the distance from p to the second nearest point in Ssetminus{p}. The 2-dispersion cost cost2(S) of S ⊂ P with |S|≥3 is minp∈S{cost2(p, S)}. Given a set P of n points and an integer k we wish to compute k point subset S of P with maximum cost2(S). In this paper we give a simple 1/({4sqrt{3}}) approximation algorithm for the problem.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019FCP0005/_p
Copier
@ARTICLE{e103-d_3_506,
author={Kazuyuki AMANO, Shin-ichi NAKANO, },
journal={IEICE TRANSACTIONS on Information},
title={An Approximation Algorithm for the 2-Dispersion Problem},
year={2020},
volume={E103-D},
number={3},
pages={506-508},
abstract={Let P be a set of points on the plane, and d(p, q) be the distance between a pair of points p, q in P. For a point p∈P and a subset S ⊂ P with |S|≥3, the 2-dispersion cost, denoted by cost2(p, S), of p with respect to S is the sum of (1) the distance from p to the nearest point in Ssetminus{p} and (2) the distance from p to the second nearest point in Ssetminus{p}. The 2-dispersion cost cost2(S) of S ⊂ P with |S|≥3 is minp∈S{cost2(p, S)}. Given a set P of n points and an integer k we wish to compute k point subset S of P with maximum cost2(S). In this paper we give a simple 1/({4sqrt{3}}) approximation algorithm for the problem.},
keywords={},
doi={10.1587/transinf.2019FCP0005},
ISSN={1745-1361},
month={March},}
Copier
TY - JOUR
TI - An Approximation Algorithm for the 2-Dispersion Problem
T2 - IEICE TRANSACTIONS on Information
SP - 506
EP - 508
AU - Kazuyuki AMANO
AU - Shin-ichi NAKANO
PY - 2020
DO - 10.1587/transinf.2019FCP0005
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2020
AB - Let P be a set of points on the plane, and d(p, q) be the distance between a pair of points p, q in P. For a point p∈P and a subset S ⊂ P with |S|≥3, the 2-dispersion cost, denoted by cost2(p, S), of p with respect to S is the sum of (1) the distance from p to the nearest point in Ssetminus{p} and (2) the distance from p to the second nearest point in Ssetminus{p}. The 2-dispersion cost cost2(S) of S ⊂ P with |S|≥3 is minp∈S{cost2(p, S)}. Given a set P of n points and an integer k we wish to compute k point subset S of P with maximum cost2(S). In this paper we give a simple 1/({4sqrt{3}}) approximation algorithm for the problem.
ER -