论文标题
通过舍入距离将令人讨厌的设施分散在图表上
Dispersing Obnoxious Facilities on Graphs by Rounding Distances
论文作者
论文摘要
我们继续研究$δ$ - 分散，这是一个连续的设施位置问题，在该图上，所有边缘具有单位长度，并且设施也可以放在边缘的内部。目的是将尽可能多的设施定位，即每两个设施彼此之间至少有$δ$的距离。我们的主要技术贡献是“汇总”距离$δ$的有效程序。 It transforms a $δ$-dispersed set $S$ into a $δ^\star$-dispersed set $S^\star$ of same size where distance $δ^\star$ is a slightly larger rational $\tfrac{a}{b}$ with a numerator $a$ upper bounded by the longest (not-induced) path in the input graph.基于此舍入步骤和与距离的连接 - $ d $独立设置问题，我们得出了许多算法结果。当通过树宽参数化时，问题在XP中。当通过TreeDepth参数化时，问题是fpt，并且在ETH下的时间复杂性上具有匹配的下限。此外，我们还可以使用我们的圆形技术将参数化的复杂性与解决方案大小作为参数来解决：$δ$ - \分散率是每个$δ\ leq 2 $ and w [1] - hard [1] - hard的每个$δ> 2 $。此外，我们表明$δ$ - 分散是每个固定的非理性距离$δ$的NP净值，这在先前的工作中被打开。
We continue the study of $δ$-dispersion, a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that every two facilities have distance at least $δ$ from each other. Our main technical contribution is an efficient procedure to `round-up' distance $δ$. It transforms a $δ$-dispersed set $S$ into a $δ^\star$-dispersed set $S^\star$ of same size where distance $δ^\star$ is a slightly larger rational $\tfrac{a}{b}$ with a numerator $a$ upper bounded by the longest (not-induced) path in the input graph. Based on this rounding procedure and connections to the distance-$d$ independent set problem we derive a number of algorithmic results. When parameterized by treewidth, the problem is in XP. When parameterized by treedepth the problem is FPT and has a matching lower bound on its time complexity under ETH. Moreover, we can also settle the parameterized complexity with the solution size as parameter using our rounding technique: $δ$-\dispersion is FPT for every $δ\leq 2$ and W[1]-hard for every $δ> 2$. Further, we show that $δ$-dispersion is NP-complete for every fixed irrational distance $δ$, which was left open in a previous work.
