Approximation Algorithms For The Euclidean Dispersion Problems

In this article, we consider the Euclidean dispersion problems. Let $P=\{p_1,p_2,\dots ,p_n\}$ be a set of $n$ points in ${\mathbb{R}}^2$. For each point $p\in P$ and $S\subseteq P$, we define $cos{t}_{\gamma }(p,S)$ as the sum of Euclidean distance from $p$ to the nearest $\gamma$ point in $S \setminus {p}$\mathrm{.}Wedefine$cost_{\gamma}(S)=\min_{p \in S}{cost_{\gamma}(p,S)}$for$S \subseteq P$\mathrm{.}Inthe$\gamma$-dispersion problem, a set $P$ of $n$ points in ${\mathbb{R}}^2$ and a positive integer $k \in [\gamma+1,n]$aregiven\mathrm{.}Theobjectiveistofindasubset$S\subseteq P$ofsize$k$suchthat$cost_{\gamma}(S)$ismaximized\mathrm{.}Weconsiderboth$2$-dispersionand$1$-dispersionproblemin$$\mathbb{R}$^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\sqrt{3}+ϵ)$-factor approximation algorithm for the $2$-dispersion problem, for any $ϵ>0$, which is an improvement over the best known approximation factor $4\sqrt{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\sqrt{3}$ for the $2$-dispersion problem in ${\mathbb{R}}^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 ${\mathbb{R}}^2$.