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

Online Median Location Problem in Common Network and Its Competitive Algorithm

作　　者：代文强[1] 

机构地区：[1]电子科技大学经济与管理学院,四川成都610054

出　　处：《系统工程》2008年第10期112-115,共4页Systems Engineering

基　　金：国家自然科学基金资助项目(70772070;70602004);电子科技大学青年科技基金资助项目

摘　　要：对一般网络上的占线中心选址问题及其竞争算法进行了研究。文献[6]证明了该问题的竞争比下界是(n-2)Δe+2((nn--21))2Δ+e2 4(n-1),其中Δe是所给空间最大的相对距离,并证明了该问题不存在常数竞争比的竞争算法。本文给出了一个多项式时间的竞争算法,并证明该算法的竞争比为ΔeΔw,其中Δw是所给空间点间的最大相对权重。所得结论不仅对于理论上占线中心选址问题的竞争算法的设计与分析,还是对于实际中的选址决策,都具有一定的指导意义。This paper studies the online median problem in common network and its competitive algorithm. The paper [6] has proved that the lower bound on the competitive ratio of this problem is （n-2）△e＋√（n-2）^△e^2＋4（n-1）/2（n-1）, where △e is the maximum ratio between any two distances, and that this problem does not exist any competitive algorithms with constant competitive ratio. In this paper we give a polynomial time competitive algorithm with the competitive ratio-△e△w, where △w is the maximum ratio between any two points weights. The obtained result is valuable not only to the design and analysis of competitive algorithm for the online median location problem in theory, but also to the location decision-making in practice.

关 键 词：运筹学 选址问题 占线中心 竞争比 一般网络 

分 类 号：O221[理学—运筹学与控制论]