Online Facility Location with Predictions
32022 Data-driven Optimization Workshop: Online Facility Location with Predictions
Speaker: Shaofeng Jiang, Peking University
In this talk, we present a nearly optimal algorithm for online facility location (OFL) with (untrusted) 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 additionally assume an untrusted predictor can suggest the facility that a demand point should be assigned to. With the access to this predictor but without knowing the error of the prediction, our algorithm achieves O(1) ratio when the error is small, which bypasses a \Omega(log n / log log n) worst-case lower bound. Furthermore, our algorithm still maintains O(log n) ratio even when the error is unbounded, nearly matching the mentioned lower bound.
Based on a joint work with Erzhi Liu, You Lyu, Zhihao Tang and Yubo Zhang.