An Approximation Algorithm for the 2-Dispersion Problem

Kazuyuki AMANO  Shin-ichi NAKANO  

IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.3   pp.506-508
Publication Date: 2020/03/01
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 —)
dispersion problem,  approximation algorithm,  

Full Text: PDF(209.1KB)>>
Buy this Article

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 pP 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.