Competitive Online Transportation Simplified

Abstract

The setting for the online transportation problem is a metric space $M$, populated by $m$ parking garages of varying capacities. Over time cars arrive in $M$, and must be irrevocably assigned to a parking garage upon arrival in a way that respects the garage capacities. The objective is to minimize the aggregate distance traveled by the cars. In 1998, Kalyanasundaram and Pruhs conjectured that there is a $(2m-1)$-competitive deterministic algorithm for the online transportation problem, matching the optimal competitive ratio for the simpler online metric matching problem. Recently, Harada and Itoh presented the first $O(m)$-competitive deterministic algorithm for the online transportation problem. Our contribution is an alternative algorithm design and analysis that we believe is simpler.