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
Deixei P ser um conjunto de pontos no plano, e d(p, q) seja a distância entre um par de pontos p, q in P. Por um ponto p∈P e um subconjunto S ⊂ P com |S|≥3, o custo de 2 dispersão, denotado por custo2(p, S), de p em relação a S é a soma de (1) a distância de p para o ponto mais próximo Ssetminus{p} e (2) a distância de p para o segundo ponto mais próximo Ssetminus{p}. O custo de 2 dispersões custo2(S) do S ⊂ P com |S|≥3 é mínimop∈S{custo2(p, S)}. Dado um conjunto P of n pontos e um número inteiro k queremos calcular k subconjunto de pontos S of P com máximo custo2(S). Neste artigo, fornecemos um algoritmo de aproximação 1/({4sqrt{3}}) simples para o problema.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -