A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
<|reference_start|>A Nearly Optimal Deterministic Algorithm for Online Transportation Problem: 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.<|reference_end|>
@article{harada2024a,
    title={A Nearly Optimal Deterministic Algorithm for Online Transportation
  Problem},
    author={Tsubasa Harada and Toshiya Itoh},
    journal={arXiv preprint arXiv:2406.03778},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.03778},
    primaryClass={cs.DS cs.DM}
}