Online Facility Location with Predictions
share
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 x_i a natural prediction f_x_i^pred which is supposed to be the facility f_x_i^opt that serves x_i in the offline optimal solution. Our main result is an O(min{lognη_∞/OPT, logn})-competitive algorithm where η_∞ is the maximum prediction error (i.e., the distance between f_x_i^pred and f_x_i^opt). Our algorithm overcomes the fundamental Ω(log n/loglog 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.
READ FULL TEXT