IEICE TRANSACTIONS on Information
An Approximation Algorithm for the 2-Dispersion Problem
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E103-D No.3 pp.506-508
- Publication Date
- 2020/03/01
- Publicized
- 2019/11/28
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2019FCP0005
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
- Category
Authors
Kazuyuki AMANO
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
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
Copy
@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},}
Copy
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 -
English
