论文标题
令人讨厌的设施位置的有效算法或圈子
Efficient Algorithms for Obnoxious Facility Location on a Line Segment or Circle
论文作者
论文摘要
我们研究了平面上令人讨厌的设施位置问题的不同限制变化。第一个是线段（COFL线）问题上受约束的令人讨厌的设施位置。我们为此问题提供了一种有效的算法，该算法在$ O（n ^ 2 \ log k + k + n \ log k \ log（n ^ 2 + k））$ time中执行。我们的结果改善了$ o（（nk）^2 \ log（nk） +（n + k）\ log（nk））$的最著名结果，由Singireddy和Basappa \ cite \ cite {Singireddydydy2022dispersing}获得的时间。我们还研究了必须将设施放在给定圆（COFL-CIRC）问题上的约束（COFL-CIRC）上的限制性圆圈（COFL-CIRC）上的相同问题。我们为此问题提供了一种有效的算法，该算法在$ O（n ^ 2 \ log k + k + n \ log k \ log（n ^ 2 + k））$ time中执行。我们的结果改善了$ o（（nk）^2 \ log（nk） +（n + k）\ log（nk））$的最著名结果，由Singireddy和Basappa \ cite \ cite {Singireddydydy2022dispersing}获得的时间。我们研究的第三个问题是Min-sum令人讨厌的设施位置（MOFL）问题。我们提供了一种有效的算法，该算法在$ O（NK \CDOTα（nk）\ log^3 {nk}）$时间中执行，其中$α（。）$是$α（。）$是倒数的Ackermann函数。最著名的先前结果是Singireddy和Basappa \ cite {Singireddy2022Dispersing}获得的$ O（n^3k）$时间。
We study different restricted variations of the obnoxious facility location problem on a plane. The first is the constrained obnoxious facility location on a line segment (COFL-Line) problem. We provide an efficient algorithm for this problem that executes in $O(n ^ 2 \log k + n \log k \log (n^2 + k))$ time. Our result improves on the best known result of $O((nk)^2 \log(nk) + (n + k) \log (nk))$ time obtained by Singireddy and Basappa\cite{singireddy2022dispersing}. We also study the same problem where the facilities must be placed on a given circle (the constrained obnoxious facility location on a circle (COFL-Circ) problem). We provide an efficient algorithm for this problem that executes in $O(n ^ 2 \log k + n \log k \log (n^2 + k))$ time. Our result improves on the best known result of $O((nk)^2 \log(nk) + (n + k) \log (nk))$ time obtained by Singireddy and Basappa\cite{singireddy2022dispersing}. The third problem we study is the min-sum obnoxious facility location (MOFL) problem.We provide an efficient algorithm that executes in $O(nk\cdot α(nk) \log^3 {nk})$ time, where $α(.)$ is the inverse Ackermann function. The best known previous result is an $O(n^3k)$ time obtained by Singireddy and Basappa\cite{singireddy2022dispersing}.
