Learning-Augmented Facility Location with Samples

Facility location is a fundamental problem in clustering and unsupervised learning. We consider the stochastic setting in which the clients arrive online from a sequence of unknown distributions. It is known (Gupta, Kehne, and Levin, SODA '24) that learning augmentation in the form of just a *single offline sample* from each distribution can significantly improve performance guarantees over the worst-case. However, this algorithm is non-robust: noisy samples invalidate the algorithmic guarantees. In this paper, we address this gap by designing the first *robust* learning-augmented algorithm for online facility location with samples. Our algorithm is robust to two natural forms of noise: adversarial corruption, in which individual samples may be manipulated, and distributional noise, in which samples are drawn from distributions that do not exactly match the corresponding input distributions. We complement our theoretical results with numerical simulations that empirically evaluate the performance and robustness of our algorithm.