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

作者：代文强; 徐寅峰; 李毅学

来源：系统工程, 2006, (08): 98-101.

• 运筹学
• 选址问题
• 占线中心
• 竞争比 Operational Research
• Facility Location Problem
• Online Median
• Competitive Ratio

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

• 单位
  西安交通大学机械制造系统工程国家重点实验室; 西安交通大学