# Approximation Algorithms For The Euclidean Dispersion Problems

Source: [Approximation Algorithms For The Euclidean Dispersion Problems](<https://www.sota2.com/research/paper/68fa6a051e209131cea2583c>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-27T06:07:38.365Z

Authors: Pawan K. Mishra, Gautam K. Das

Published: 2021-05-19T15:56:30.000Z

## Abstract

In this article, we consider the Euclidean dispersion problems. Let $P=\\{p\_{1}, p\_{2}, \\ldots, p\_{n}\\}$ be a set of $n$ points in $\\mathbb{R}^2$. For each point $p \\in P$ and $S \\subseteq P$, we define $cost\_{\\gamma}(p,S)$ as the sum of Euclidean distance from $p$ to the nearest $\\gamma $ point in $S \\setminus \\{p\\}$. We define $cost\_{\\gamma}(S)=\\min\_{p \\in S}\\{cost\_{\\gamma}(p,S)\\}$ for $S \\subseteq P$. In the $\\gamma$-dispersion problem, a set $P$ of $n$ points in $\\mathbb{R}^2$ and a positive integer $k \\in \[\\gamma+1,n\]$ are given. The objective is to find a subset $S\\subseteq P$ of size $k$ such that $cost\_{\\gamma}(S)$ is maximized. We consider both $2$-dispersion and $1$-dispersion problem in $\\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 + \\epsilon )$-factor approximation algorithm for the $2$-dispersion problem, for any $\\epsilon \> 0$, which is an improvement over the best known approximation factor $4\\sqrt3$ \[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$.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2105.09217>)

[PDF](<https://arxiv.org/pdf/2105.09217.pdf>)