Paper Info
Title
An Approximation Algorithm For The 2-Dispersion Problem
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 subset of P with vertical bar S vertical bar >= 3, the 2-dispersion cost, denoted by cost(2)( p, S), of p with respect to S is the sum of (1) the distance from p to the nearest point in S\{p} and (2) the distance from p to the second nearest point in S\{p}. The 2-dispersion cost cost(2)(S) of S subset of P with vertical bar S vertical bar >= 3 is min(p is an element of S) {cost(2)( 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 cost(2)(S). In this paper we give a simple 1/(4 root 3) approximation algorithm for the problem.
Year
DOI
Venue
2020
10.1587/transinf.2019FCP0005
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
Keywords
Field
DocType
dispersion problem, approximation algorithm
Approximation algorithm,Dispersion (optics),Computer vision,Computer science,Algorithm,Artificial intelligence
Journal
Volume
Issue
ISSN
E103D
3
1745-1361
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Kazuyuki Amano1314.60
Shin-ichi Nakano224624.40