# Approximation Algorithms For The Dispersion Problems in a Metric Space Source: [Approximation Algorithms For The Dispersion Problems in a Metric Space]() Collection index: [llms.txt]() Data updated: 2025-10-25T23:16:37.291Z Authors: Pawan K. Mishra, Gautam K. Das Published: 2021-05-19T16:01:21.000Z ## Abstract In this article, we consider the $c$-dispersion problem in a metric space $(X,d)$. Let $P=\\{p\_{1}, p\_{2}, \\ldots, p\_{n}\\}$ be a set of $n$ points in a metric space $(X,d)$. For each point $p \\in P$ and $S \\subseteq P$, we define $cost\_{c}(p,S)$ as the sum of distances from $p$ to the nearest $c $ points in $S \\setminus \\{p\\}$, where $c\\geq 1$ is a fixed integer. We define $cost\_{c}(S)=\\min\_{p \\in S}\\{cost\_{c}(p,S)\\}$ for $S \\subseteq P$. In the $c$-dispersion problem, a set $P$ of $n$ points in a metric space $(X,d)$ and a positive integer $k \\in \[c+1,n\]$ are given. The objective is to find a subset $S\\subseteq P$ of size $k$ such that $cost\_{c}(S)$ is maximized. We propose a simple polynomial time greedy algorithm that produces a $2c$-factor approximation result for the $c$-dispersion problem in a metric space. The best known result for the $c$-dispersion problem in the Euclidean metric space $(X,d)$ is $2c^2$, where $P \\subseteq \\mathbb{R}^2$ and the distance function is Euclidean distance \[ Amano, K. and Nakano, S. I., Away from Rivals, CCCG, pp.68-71, 2018 \]. We also prove that the $c$-dispersion problem in a metric space is $W\[1\]$-hard. ## 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]() [PDF]()