2024/06/06 by Tsubasa Harada, Harada, Tsubasa, Toshiya Itoh +1 · 2 citations
Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Smart Parking Systems Research #Transportation and Mobility Innovations
paper · pdf · doi:10.48550/arxiv.2406.03778
openalex publication_date 2024/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.