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
Mari P menjadi satu set mata pada satah, dan d(p, q) ialah jarak antara sepasang mata p, q in P. Untuk satu titik p∈P dan subset S ⊂ P dengan |S|≥3, kos 2 penyebaran, dilambangkan dengan kos2(p, S), daripada p berkenaan dengan S ialah hasil tambah (1) jarak dari p ke titik terdekat dalam Ssetminus{p} dan (2) jarak dari p ke titik kedua terdekat dalam Ssetminus{p}. Kos 2 penyebaran kos2(S) daripada S ⊂ P dengan |S|≥3 ialah minp∈S{kos2(p, S)}. Diberi satu set P of n mata dan integer k kami ingin mengira k subset titik S of P dengan maksimum kos2(S). Dalam kertas ini kami memberikan algoritma penghampiran 1/({4sqrt{3}}) mudah untuk masalah itu.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -