2026/07/21 by Tom Janßen
Computer Science · #cs.DS
We consider a continuous facility location problem called δ-Dispersion. For some fixed δ> 0, the goal is to place as many facilities on a graph as possible with pairwise distance at least δ. The facilities may be located on the vertices of the graph, or the interior of the edges. This problem can be interpreted as a continuous version of the well-known Independent Set problem. Its approximation behavior is very similar for large values of δ. Notably, Grigoriev et al. [Algorithmica 21] showed that δ-Dispersion is solvable in polynomial time when δ= 1/x or δ= 2/x for a natural number x and NP-hard otherwise. We study the approximability of δ-Dispersion depending on the value of δ. For δ> 2, we show poly-APX-hardness, while for all δ< 2 that are not solvable in polynomial time we show APX-hardness. Thanks to a translation theorem for δ due to Hartmann et al. [MFCS 22], we may focus our attention for approximation algorithms on the intervals (2/3 , 1) and (1, 2). We provide several approximation algorithms with an approximation factor approaching 1 as δ approaches one of the interval boundaries. Surprisingly, the behavior as δ approaches 2/3 from above is different: As our hardness reductions reveal, it is impossible (under standard complexity-theoretic assumptions) to construct an approximation algorithm with an approximation factor approaching 1 as δ approaches 2/3 from above.