Online Median Location Problem in Common Network and Its Competitive Algorithm
Wenqiang Dai · Systems Engineering · 2008
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)2Δ2e+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.