Near-Optimal Deterministic Online Transportation

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 for the online transportation problem and show that it achieves a competitive ratio of at most \(8m-13\) . This is the first \(O(m)\) -competitive deterministic algorithm, coming close to the lower bound of \(2m-1\) within a constant factor.