Approximation Algorithms For The Euclidean Dispersion Problems
share
In this article, we consider the Euclidean dispersion problems. Let P={p_1, p_2, …, p_n} be a set of n points in ℝ^2. For each point p ∈ P and S ⊆ P, we define cost_γ(p,S) as the sum of Euclidean distance from p to the nearest γ point in S ∖{p}. We define cost_γ(S)=min_p ∈ S{cost_γ(p,S)} for S ⊆ P. In the γ-dispersion problem, a set P of n points in ℝ^2 and a positive integer k ∈ [γ+1,n] are given. The objective is to find a subset S⊆ P of size k such that cost_γ(S) is maximized. We consider both 2-dispersion and 1-dispersion problem in ℝ^2. Along with these, we also consider 2-dispersion problem when points are placed on a line. In this paper, we propose a simple polynomial time (2√(3) + ϵ )-factor approximation algorithm for the 2-dispersion problem, for any ϵ > 0, which is an improvement over the best known approximation factor 4√(3) [Amano, K. and Nakano, S. I., An approximation algorithm for the 2-dispersion problem, IEICE Transactions on Information and Systems, Vol. 103(3), pp. 506-508, 2020]. Next, we develop a common framework for designing an approximation algorithm for the Euclidean dispersion problem. With this common framework, we improve the approximation factor to 2√(3) for the 2-dispersion problem in ℝ^2. Using the same framework, we propose a polynomial time algorithm, which returns an optimal solution for the 2-dispersion problem when points are placed on a line. Moreover, to show the effectiveness of the framework, we also propose a 2-factor approximation algorithm for the 1-dispersion problem in ℝ^2.
READ FULL TEXT