占线中心选址问题竞争比的下界

Lower Bound for the Competitive Ratio of Online Median Problem

对占线中心选址问题的竞争比进行了研究。对度量空间占线中心选址问题,本文证明该问题的下界是2-n-n n-2-13n+3,其中n为空间点的个数,该结果要优于已有的结果2-n-21。对一般空间上的占线中心选址问题,本文证明了竞争比的下界是(n-2)Δ+2((nn--21))2Δ2+4(n-2),其中Δ是所给空间最大的相对距离,并证明一般空间上的占线中心选址问题不存在常数竞争算法。

This paper studies the competitive ratio of online median problem. For the case being the metric space, we prove the lower bound is 2-（n-√n^2-3n＋3/n-1）, where n is the number of points in the space. This result is better than the existed result 2-（2/n-1）.For the case being the common space, this paper proves the lower bound is （（n-2）△＋√（n-2）^2△^2＋4（n-2））/2（n-1）,where △ is the maximal comparative ratio of points distances. We also prove that there＇s no constant competitive ratio algorithm for this case.