Robust Algorithms for Facility Location with Noisy Predictions

We investigate the fundamental problem of facility location in settings where algorithms receive noisy predictions about the optimal solution. Motivated by real-world scenarios in which side information from historical data or machine learning models is imperfect, we develop robust algorithms that effectively leverage these noisy predictors while maintaining provable guarantees. We study three distinct models for prediction noise. In the first model, each client is assigned a predicted cluster label, and the predictor may mislabel up to an $\alpha$ fraction of the clients within each true cluster and within each predicted cluster. In the second model, the algorithm can issue pairwise queries asking whether two clients are served by the same facility in an optimal solution, and each response is independently corrupted with probability at most $\alpha <1/2$. In the third model, the predictor provides a candidate set of facilities that may include ${\eta }^{+}$ false positives and ${\eta }^{-}$ false negatives relative to an optimal solution. For the Uncapacitated Facility Location (UFL) problem, we obtain several results under these noise models. With a noisy label predictor, we achieve a $(1+O(\alpha ))$-approximation provided the error rate $\alpha <1/2$. Using noisy pairwise queries, we obtain a $(1+\epsilon )$-approximation algorithm with query complexity $$\begin{gathered} widetildeO \\ left( \\ max \\ left \\ frac| \\ mathcalC|k(1-2 \\ alpha{)}^4{s}_{ \\ min}, \\ frac| \\ mathcalC| \\ delta{s}_{ \\ min} \\ right \\ right) \end{gathered}$$ where $\mathcal{C}$ is the set of clients, $k$ is the number of clusters in the fixed optimum, and $s_{\min }$ is the minimum optimal cluster size. We complement the oracle results with an ETH-based query lower bound: for a constant ${\beta }_0>0$ any subexponential-time $(1+\beta )$-approximation with $\beta <{\beta }_0$ must satisfy $q_1\log k+q_2=\Omega (k^{1-o(1)})$, where $q_1$ and $q_2$ are the numbers of label and pairwise queries. Finally, given a predicted facility set, we design an algorithm whose approximation guarantee degrades linearly with the opening-cost masses ${\eta }^{+}$ and ${\eta }^{-}$. We also show that such linear dependence on both error parameters is unavoidable in the high-accuracy regime. Together, these results establish a clear trade-off between prediction quality and approximation performance for the facility location problem across a variety of practical noise models.