Online Rounding and Learning Augmented Algorithms for Facility Location

Facility Location is a fundamental problem in clustering and unsupervised learning. Recently, significant attention has been given to studying this problem in the classical online setting enhanced with machine learning advice. While (almost) tight bounds exist for the fractional version of the problem, the integral version remains less understood, with only weaker results available. In this paper, we address this gap by presenting the first online rounding algorithms for the facility location problem, and by showing their applications to online facility location with machine learning advice. Beyond its implications for the learning augmented setting, our results also show that the hardness of the classic online facility location problem lies in computing a good fractional solution and not in rounding it.