Overview
This study examines the approximability of the continuous facility location problem known as $\delta$-Dispersion. The problem involves placing the maximum possible number of facilities on a graph—either on vertices or along the interior of edges—such that the pairwise distance between any two facilities is at least $\delta$, where $\delta \geq 0$ is a fixed value. This problem is framed as a continuous variant of the Independent Set problem.
Research Context
The $\delta$-Dispersion problem shares approximation characteristics with the Independent Set problem, particularly for larger values of $\delta$. Previous work by Grigoriev et al. (Algorithmica 21) established that $\delta$-Dispersion is solvable in polynomial time when $\delta = 1/x$ or $\delta = 2/x$ for a natural number $x$. Conversely, for all other values of $\delta$, the problem is NP-hard. This current research builds upon this foundation by investigating its approximability across a range of $\delta$ values.
Approach
The researchers analyzed the approximability of $\delta$-Dispersion based on the value of $\delta$. They identified specific hardness results for different ranges of $\delta$. A translation theorem for $\delta$ by Hartmann et al. (MFCS 22) allowed the focus for approximation algorithm development to be narrowed to the intervals $(2/3, 1)$ and $(1, 2)$. Within these intervals, the study aimed to provide approximation algorithms and explore their performance. Hardness reductions were also employed to understand limits on approximation factors.
Findings
- For $\delta \leq 2$, the $\delta$-Dispersion problem is poly-APX-hard.
- For all $\delta > 2$ that are not solvable in polynomial time, the problem is APX-hard.
- Within the intervals $(2/3, 1)$ and $(1, 2)$, several approximation algorithms were developed. These algorithms exhibit an approximation factor that approaches $1$ as $\delta$ nears the boundaries of these intervals.
- A different behavior was observed as $\delta$ approaches $2/3$ from above. Hardness reductions indicate that, under standard complexity-theoretic assumptions, it is not possible to construct an approximation algorithm with an approximation factor approaching $1$ in this specific scenario.