Competitive Online Transportation Simplified

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.