  For the online transportation problem with $m$ server sites, it has long been
known that the competitive ratio of any deterministic algorithm is at least
$2m-1$. Kalyanasundaram and Pruhs conjectured in 1998 that a deterministic
$(2m-1)$-competitive algorithm exists for this problem, a conjecture that has
remained open for over two decades.
  In this paper, we propose a new deterministic algorithm named
Subtree-Decomposition for the online transportation problem and show that it
achieves a competitive ratio of at most $8m-5$. This is the first
$O(m)$-competitive deterministic algorithm, coming close to the lower bound of
$2m-1$ within a constant factor.
