A Robustified Greedy Algorithm for Online Transportation with Improved Competitive Guarantees

Ritesh Seth, Syamantak Das, Sharath Raghvendra

We study the \emph{online transportation problem}, in which $n$ requests arriving sequentially in a metric space must be irrevocably assigned to $k$ capacitated facilities. Beyond…