Resource Augmentation Analysis of the Greedy Algorithm for the Online Transportation Problem

Abstract

We consider the online transportation problem set in a metric space containing parking garages of various capacities. Cars arrive over time, and must be assigned to an unfull parking garage upon their arrival. The objective is to minimize the aggregate distance that cars have to travel to their assigned parking garage. We show that the natural greedy algorithm, augmented with garages of $k\ge 3$ times the capacity, is $\left(1+\frac{2}{k-2}\right)$-competitive.