Smoothed Analysis of Online Metric Problems

Christian Coester, Jack Umenberger

We study three classical online problems -- $k$-server, $k$-taxi, and chasing size $k$ sets -- through a lens of smoothed analysis. Our setting allows request locations to be adver…