Online Facility Location with Predictions

We provide nearly optimal algorithms for online facility location (OFL) with predictions. In OFL, n demand points arrive in order and the algorithm must irrevocably assign each demand point to an open facility upon its arrival. The objective is to minimize the total connection costs from demand points to assigned facilities plus the facility opening cost. We further assume the algorithm is additionally given for each demand point xi a natural prediction fxipred which is supposed to be the facility fxiopt that serves xi in the offline optimal solution. Our main result is an O(minlog fracnη_∞OPT, logn )-competitive algorithm where η_∞ is the maximum prediction error (i.e., the distance between fxipred and fxiopt). Our algorithm overcomes the fundamental Omega(fraclog nlog log n) lower bound of OFL (without predictions) when η_∞ is small, and it still maintains O(log n) ratio even when η_∞ is unbounded. Furthermore, our theoretical analysis is supported by empirical evaluations for the tradeoffs between η_∞ and the competitive ratio on various real datasets of different types.