Key points are not available for this paper at this time.
We propose a new deterministic algorithm called Subtree-Decomposition for the online transportation problem and show that the algorithm is (8m-5) -competitive, where m is the number of server sites. It has long been known that the competitive ratio of any deterministic algorithm is lower bounded by 2m-1 for this problem. On the other hand, the conjecture proposed by Kalyanasundaram and Pruhs in 1998 asking whether a deterministic (2m-1) -competitive algorithm exists for the online transportation problem has remained open for over two decades. The upper bound on the competitive ratio, 8m-5, which is the result of this paper, is the first to come close to this conjecture, and is the best possible within a constant factor.
Harada et al. (Thu,) studied this question.