一般网络上的占线中心选址问题及其竞争算法

摘要

对一般网络上的占线中心选址问题及其竞争算法进行了研究。文献[6]证明了该问题的竞争比下界是(n-2)Δe+2((nn--21))2Δ+e2 4(n-1),其中Δe是所给空间最大的相对距离,并证明了该问题不存在常数竞争比的竞争算法。本文给出了一个多项式时间的竞争算法,并证明该算法的竞争比为ΔeΔw,其中Δw是所给空间点间的最大相对权重。所得结论不仅对于理论上占线中心选址问题的竞争算法的设计与分析,还是对于实际中的选址决策,都具有一定的指导意义。