acceptodds
Under review as a conference paper at ICLR 2027

Robust Algorithms for Facility Location with Noisy Predictions

Abstract

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 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 . In the third model, the predictor provides a candidate set of facilities that may include false positives and 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 -approximation provided the error rate . Using noisy pairwise queries, we obtain a -approximation algorithm with query complexity where is the set of clients, is the number of clusters in the fixed optimum, and is the minimum optimal cluster size. We complement the oracle results with an ETH-based query lower bound: for a constant any subexponential-time -approximation with must satisfy , where and 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 and . 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.

Primary area:
learning theory
Keywords:
Approximation algorithms, Learning-augmented algorithms, Facility Location

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.40 over 5 reviews, above 9% of the others.
Reviewer_gRHKOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies metric Uncapacitated Facility Location (UFL) under three different noisy prediction models. The input to the UFL problem is a set of facilities FF, and clients CC, each facility has an associated opening cost. The goal is output a subset of facilities SS that minimizes the sum of the facility opening costs plus the sum of the distances from each client to the closest facility. (The predictions of each model are with respect to some fixed optimal solution S∗S^* with kk facilities.)

  • M1: In this model predicted label is given to each client from a set [k][k]. After relabeling (a map from [k][k] to FF), the predicted clusters are required to have precision and recall of 1−α1-\alpha wrt S∗S^*. The basic algorithm groups clients by their predicted label and for each cluster computes the facility that minimizes the cost. They obtain a 1+O(α)1 + O(\alpha) approximation for α<1/2\alpha < 1/2. Another algorithm that must query the predicted labels is similar, results in another (1+ε)(1+\varepsilon) factor in the approximation.

  • M2: In this model the algorithm can ask whether two clients belong to the same cluster in the fixed optimal solution. The answer can be wrong with some probability α\alpha, and onced queried is fixed (no boosting). The algorithm takes a sample, then uses an algorithm from prior work to recover the clusters inferred from the sample, then uses the same procedure as in M1.

  • M3: In this model the predictor gives a set of facilities, error is quantified by the sum of opening facility costs of those facilities predicted but not optimal, and also the sum for those optimal but not predicted. Their algorithm assumes that access to a bicriteria approximation algorithm is given and mostly uses this algorithm as a black box.

Finally, the paper gives ETH-based query lower bound in M1/M2.

Critical strengths

None.

Critical weaknesses

The biggest weakness to me is that the algorithms seem to contain very little facility-location algorithmic ideas. In M1, the predictor essentially already provides the solution up to some relabeling. The algorithm 1 just says to compute the new label. The clusters given are used as-is. And the query version algorithm is essentially the same, but with samples. The analysis is a straightforward PAC-learning-like probabilistic argument. There's no interesting idea here. M2 is the same story, which the only interesting step being the cluster recovery, which is just a blackbox use of prior work. Then the problem reduces to M1. The algorithm given for M3 is also a blackbox use of prior work.

Questions for authors
  • How do your results improve prior work? The introduction makes the explicit contribution unclear.
2 comments

We thank the reviewer for emphasizing the need to clarify our technical contributions and their relationship to prior work. We have revised the manuscript and expanded the introduction accordingly. We agree that grouping clients by predictions and using a clustering subroutine are natural high-level approaches. The main issue, however, is how to turn such noisy information into guarantees for the facility-location objective, where facility-opening and connection costs behave differently.

1. M1: Cost-aware sampling and transfer (Section 3, Appendix G). Even perfect cluster labels do not identify the facilities to open: each predicted group still requires a joint opening-cost/connection-cost decision. Unlike kk-median, opening costs are incurred once, whereas sampled connection costs must be rescaled to represent all clients. In particular, estimating cluster sizes and normalizing opening costs can change which facility is preferred, even if the connection-cost estimates are accurate.

To avoid this problem, our algorithm uses a single uniform sample and minimizes

fv+nm∑j∈U∩Xid(j,v),f_v+\frac{n}{m}\sum_{j\in U\cap X_i}d(j,v),

without estimating cluster sizes. The proof does not apply a standard concentration bound to absolute distances without a uniform distance bound. Instead, we compare each candidate vv with a reference facility qq and use ∣d(j,v)−d(j,q)∣≤d(v,q)|d(j,v)-d(j,q)|\le d(v,q). Concentrating these cost differences uniformly over candidates ensures that the comparison remains valid for the facility chosen adaptively from the sample.

A separate transfer lemma handles noisy labels. If the predicted cluster XX and reference cluster YY have two-sided overlap at least 1−α1-\alpha, and

cost(X,p)−cost(X,q)≤ξ∣X∣d(p,q),\mathrm{cost}(X,p)-\mathrm{cost}(X,q)\le\xi|X|d(p,q),

then cost(Y,p)≤(1+β)/(1−β) cost(Y,q)\mathrm{cost}(Y,p)\le(1+\beta)/(1-\beta)\,\mathrm{cost}(Y,q), where β=2α+ξ/(1−α)\beta=2\alpha+\xi/(1-\alpha). The opening-cost difference is preserved in this transfer. Combining the two lemmas yields the (1+2α)/(1−2α)⋅(1+ε)(1+2\alpha)/(1-2\alpha)\cdot(1+\varepsilon) guarantee. Thus, the contribution is not simply grouping predicted labels, but controlling the opening/connection-cost balance under both label noise and sampling.

2. M2: Recovery from persistent noisy pairwise answers (Section 4, Appendix H). We build on noisy-query clustering, but the revised algorithm does not assume access to a black-box exact partition oracle. We analyze a signed-SDP pilot using an explicit dual certificate, prove a quantitative objective-gap bound that permits rounding approximate SDP solutions, and handle independent but heterogeneous flip probabilities puv≤αp_{uv}\le\alpha. Since an oracle returns the same answer whenever a pair is repeated, conventional repeated-query boosting is unavailable. We therefore classify additional sampled clients using fresh, previously unqueried pairs; conditional on the pilot, the majority tests retain the required independence. We charge every distinct pair in both stages, obtaining (b2)+(m−b)kr\binom{b}{2}+(m-b)kr queries, and explicitly state the pilot-feasibility requirement b≤nb\le n. These details are needed to turn recovered clusters into a valid UFL approximation with a justified query bound.

3. M3 and complementary results (Sections 5–6). We use modified opening costs and a strong-comparator UFL bifactor algorithm to prove

E[cost(T)]≤λcOPT+η++(λf−λc)η−.\mathbb E[\mathrm{cost}(T)]\le\lambda_c\mathrm{OPT}+\eta_++(\lambda_f-\lambda_c)\eta_-.

Unlike directly trusting the predicted facility set, this guarantee depends on opening-cost prediction errors and can remain informative even if its connection cost is arbitrarily large. We also establish matching leading coefficients in the small-error regime. Separately, maximum-weight matching solves UFL exactly when an optimal clustering has parts of size at most two, whereas the problem remains APX-hard for parts of size at most three.

Relationship to prior work. Ergun et al. (2022) and Fan and Shin (2025) study learning-augmented clustering; Mazumdar and Saha (2017) and Peng and Zhang (2021) study noisy partition recovery. Their clustering objectives do not include UFL's one-time opening costs. Jiang et al. (2022) study online facility location with predictions, whereas we study offline instances with noisy structural advice. Antoniadis et al. (2025) develop a general predicted-subset framework; our M3 analysis additionally controls client connections through a UFL-specific bifactor argument. We do not claim that concentration inequalities, SDPs, or bifactor algorithms are new in isolation. Our contributions are the cost-aware transfer and sampling arguments, the quantitative recovery-to-UFL analysis under persistent noise, and the corresponding structural bounds and hardness results.

I thank the authors for their response. I agree with the other reviewers, the technical contribution still seems too low for such a competitive venue. My score remains unchanged.

Reviewer_Q7xbOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers learning-augmented facility location in three different models.

  1. The prediction partitions the clients into clusters, each presumed to be served by a facility. The noise in the prediction is in the form of a fraction of clients in a predicted cluster actually belonging to other clusters in a reference optimal solution.
  2. The prediction returns if a queried pair of clients is in the same cluster or different clusters in a reference optimal solution. The noise is quantified by the probability that this Boolean query is answered incorrectly by the predictor.

For these two forms of prediction, the main results are about query complexity. (In the full information setting, results for these prediction models are already known.)

  1. The third prediction gives the set of open facilities. Noise is of two types: false positives and false negatives.

In the third category, the main result is an approximation algorithm in the full information setting, i.e., when the predicted answers to all queries are known to the algorithm.

In addition to these algorithmic results, the paper also gives various lower bounds to complement the upper bounds.

Critical strengths

The noise models are natural candidates for facility location with predictions. Therefore, the direction of research seems quite natural within the ambit of algorithms with predictions.

Critical weaknesses

The algorithms are generally the obvious ones. and in general, most of the heavy lifting already comes from prior work that considers the full information setting. So, while the direction of research is a natural one, these specific results seem quite straightforward.

Questions for authors

This is not a question specifically, but as a suggestion, it would be good to isolate parts of the work that have some interesting technical content, e.g., that do not follow the natural algorithmic strategy or deviate from what one would normally expect from a standard use of tail bounds.

2 comments

We thank the reviewer for the constructive suggestion. We have uploaded a revised manuscript to OpenReview, with more clear Introduction, additional technical analyses and results.

While the high-level algorithmic strategies are natural, our main technical contributions concern how to make these strategies work with limited and noisy predictions in facility location. We would like to highlight two methodological contributions.

1. M1: A sampling method that preserves facility-opening costs.

A key difficulty in UFL is that facility-opening costs are paid once, whereas connection costs scale with the number of sampled clients. Standard sampling approaches that estimate cluster sizes and rescale opening costs can therefore select the wrong facility, even with perfect predictions.

To address this, we develop a single-stage sampling algorithm that minimizes

fv+nm∑j∈U∩Xid(j,v),f_v+\frac{n}{m}\sum_{j\in U\cap X_i}d(j,v),

without estimating cluster sizes.

The main technical idea is to concentrate differences between facility costs, rather than their absolute values. By the triangle inequality,

∣d(j,v)−d(j,q)∣≤d(v,q),|d(j,v)-d(j,q)|\leq d(v,q),

so the estimation error can be controlled relative to the distance between candidate facilities, without requiring bounded absolute distances.

Importantly, the opening-cost difference is preserved exactly in this comparison. We then establish a deterministic cost-contrast transfer lemma (Lemma 1 and Lemma G.1), which transfers the empirical comparison from a predicted cluster to its reference cluster under two-sided label noise.

The combination of contrast-based concentration and deterministic transfer is what allows our sampling algorithm to maintain the opening-cost/connection-cost balance. This is the main technical distinction from standard sampling analyses for center-based clustering (Section 3 and Appendix G).

2. M2: Recovering and extending a partition under persistent noisy queries.

For M2, the challenge is that pairwise queries do not directly provide cluster labels, and repeated queries to the same pair return persistent answers. Thus, simply applying a noisy-clustering routine to a random sample does not by itself establish the required query complexity or justify the subsequent classification step.

Our method separates recovery and classification into two stages.

First, we recover a pilot partition through a signed SDP. We establish a quantitative dual certificate and rounding guarantee that ensure exact recovery under an explicit cluster-size condition.

Second, we classify the remaining sampled clients using fresh pairwise queries to representatives of the recovered pilot clusters. Since these pairs were not used during pilot recovery, the required independence is preserved even after conditioning on the pilot.

The analysis also accommodates heterogeneous independent error probabilities through a coupling argument. We explicitly account for all queries, including those used for SDP recovery and subsequent classification:

(b2)+(m−b)kr.\binom{b}{2}+(m-b)kr.

Thus, our contribution is not simply invoking an existing noisy-clustering algorithm, but establishing a complete recovery-and-classification procedure with a quantitative recovery guarantee and explicit query complexity (Section 4 and Appendix H).

3. M3: Tight structural-error penalties.

Optimizing the bifactor parameter gives a small-error bound of

OPT+η++(1+o(1))η−log⁡(OPT/η−)\mathrm{OPT}+\eta^++(1+o(1))\eta^-\log(\mathrm{OPT}/\eta^-).

We prove that neither leading coefficient can be reduced in polynomial time unless P=NP. The false-positive bound reduces from Maximum Independent Set (via Vertex Cover), and the false-negative bound from Set Cover. Singleton padding makes η±/OPT→0\eta^\pm/\mathrm{OPT}\to0 while a 1−o(1)1-o(1) fraction of optimal facilities are predicted correctly. Thus, the bounds remain tight even for nearly perfect predictions, without ETH-type assumptions (Section 5, Appendix F).

4. A sharp cluster-size threshold.

When all optimal clusters have size at most two, we evaluate the cheapest facility for every singleton/pair, then use maximum-weight matching to select disjoint pairs. This solves UFL exactly without prediction queries.

Conversely, degree-splitting reduces 4-regular Vertex Cover to a subcubic graph, whose incidence metric has unit opening costs and distances in {1,2,3}\{1,2,3\}. Every opened facility serves at most three edge-clients, while the Vertex Cover gap is preserved. Hence UFL remains APX-hard with optimal cluster sizes at most three (Section 6).

We have revised the introduction to emphasize the methodological contributions of M1 and M2 and clarify how they differ from existing clustering techniques.

We appreciate the reviewer's suggestion, which helped us better explain the technical ideas underlying our results.

Thanks for the rebuttal response. My opinion of the paper remains unchanged. The problem setting is reasonably natural, but the paper does not seem the technical quality required for a competitive venue in my opinion. I will keep my score unchanged.

Reviewer_mvY2OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies metric uncapacitated facility location under three noisy prediction models: client cluster labels, pairwise same-cluster queries, and predicted facility sets. It proposes algorithms with approximation guarantees depending on prediction quality, including a (1+ε)(1+\varepsilon)-approximation under noisy pairwise queries and sampling-based methods to reduce query complexity. It also establishes ETH-based query lower bounds and lower bounds on the dependence of solution cost on prediction errors.

Critical strengths

The paper provides provable approximation guarantees for facility location under three noisy prediction models, including query-efficient algorithms and a (1+ε)(1+\varepsilon)-approximation. Complementary lower bounds strengthen the theoretical contribution.

Critical weaknesses

The prediction assumptions appear demanding and lack empirical justification. M1 requires precision and recall above 1/21/2 for every optimal cluster, while M2 requires independently noisy same-cluster answers relative to an exact optimum. It is unclear whether practical predictors can capture this structure. Defining prediction errors relative to a γ\gamma-approximate solution (with an additional factor of γ\gamma in the guarantee), rather than restricted to optimal solution only, would broaden applicability. However, given existing fast algorithms with low approximation ratios, the practical advantage remains unclear without experiments.

Questions for authors

See Weakness.

1 comment

We thank the reviewer for these helpful suggestions. We agree that the prediction assumptions deserve further discussion and that empirical comparisons can help clarify when structural predictions provide advantages over classical facility-location algorithms.

1. Predictions relative to an approximately optimal solution.

We agree with the suggested extension. Importantly, our upper-bound arguments do not require predictions to describe an exact optimal solution.

Let RR be any fixed feasible reference facility set satisfying

c(R)≤ρ OPT,ρ≥1,c(R)\leq \rho\,\mathrm{OPT},\qquad \rho\geq 1,

and define the prediction assumptions with respect to the client partition induced by RR.

For M1, the cost-contrast transfer lemma and sampling analysis apply to this reference partition without requiring RR to be optimal. Consequently, with probability at least 1−δ1-\delta,

\leq \frac{1+2\alpha}{1-2\alpha}(1+\varepsilon)c(R) \leq \rho\frac{1+2\alpha}{1-2\alpha} (1+\varepsilon)\mathrm{OPT}.$$ For **M2**, recovery and classification concern the reference partition. Provided the pilot-feasibility condition of our revised M2 theorem holds for the reference clusters, the facility-cost analysis similarly yields, with probability at least $1-\delta$, $$c(\widehat S) \leq (1+\varepsilon)c(R) \leq \rho(1+\varepsilon)\mathrm{OPT}.$$ The query-bound formulas remain valid when evaluated using the number and imbalance of the reference clusters. For **M3**, the opening-cost-sensitive guarantee also extends to prediction errors measured relative to $R$. These extensions are formally established in the new *Approximate-reference guarantees* corollary of our revised manuscript. Thus, our framework accommodates predictions associated with approximately optimal solutions, although the corresponding prediction-quality assumptions for M1 and pilot-feasibility condition for M2 still apply. **2. Experimental comparison with classical algorithms.** We agree that empirical evaluation is valuable. Motivated by this concern, we conducted controlled experiments on five families of synthetic metric UFL instances, including balanced and imbalanced Gaussian clusters, tree shortest-path metrics, and two planted-coverage constructions. We compared our sampling-based algorithm against multi-start 2-exchange local search and computed the optimal UFL costs using integer programming. On the four-cluster planted-coverage instances, with 10% independently corrupted client labels and a 50% sampling rate, the results over 60 random instances were: - **Our algorithm:** average cost $1.0003\,\mathrm{OPT}$. - **Multi-start 2-exchange:** average cost $1.0355\,\mathrm{OPT}$. - **Comparison:** our algorithm achieved strictly lower cost in 58 of 60 instances. The planted clusters corresponded to an optimal facility solution and satisfied the M1 precision/recall requirements in those 58 instances. These are valid non-Euclidean metric instances designed to expose difficulties for local search. We emphasize that the improvements are instance-dependent. On Gaussian and tree-metric instances, multi-start local search typically found the optimum, leaving little room for improvement. The experiments therefore illustrate settings where accurate structural predictions help, rather than establishing uniform superiority over classical algorithms. **3. Feasibility and limitations of noisy pairwise predictions.** We also investigated M2 using persistent, independently corrupted pairwise answers. On the four-cluster synthetic instances, with pairwise error probability $\alpha=0.1$, a pilot of 96 clients and 13 representatives per cluster achieved exact sample-partition recovery in 5 of 6 runs. The mean facility-location cost was $1.0241\,\mathrm{OPT}$, compared with $1.0343\,\mathrm{OPT}$ for multi-start 2-exchange local search. A complete run required 9,968 pairwise queries, compared with 28,680 possible client pairs. At $\alpha=0.2$, recovery became less reliable. These experiments highlight the trade-off between prediction accuracy, query complexity, and solution quality. We acknowledge that independence of pairwise prediction errors is a modeling assumption and that synthetic experiments alone cannot establish its validity for practical predictors. Our theoretical results characterize the benefits of structural predictions under explicit assumptions; the experiments help identify both their potential advantages and their limitations. **We will add these experimental results, together with the implementation details and limitations, to the revised manuscript.** Thank you again for the constructive suggestions.
Reviewer_4nB9OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper considers facility location problem under noisy prediction models. Precisely, it considers UFL under three variants of noisy prodiction models. In the first model, one is given access to a noisy label predictor with inaccurate fraction α\alpha and the goal is to find 1+O(α)1+O(\alpha) approximation solution. The second model is a noisy pairwise query model, which is common in clustering problem, the goal is to find an 1+ϵ1+\epsilon-approximation by using as small as possible queries. In the third model, one is given a candidate solution as a reference, and the approximation ratio is related to the quality of the reference solution.

Previously, most research on algorithm design under noisy prediction model focus on center based clustering, in which a assuming the knowledge of groud truth is natural. For UFL, a point is to balance the trade-off of openning cost and connection cost, thus assuming a unique groud truth appears to be less natural than it does in clustering. Moreover, unlike clustering, the structure of facility location means assuming a high quality prediction of the openning facility makes the problem much easier. As a result, UFL under noisy prediction models are less interesting than k-means or k-median clsutering.

Critical strengths

This paper provides a comprehensive study of facility location under noisy prediction models. Both upper and lower bounds have been established. Comparing with clustering, works on facility location under noisy prediction models were relatively limited.

Critical weaknesses

As discussed in paper summary, noisy prediction models for facility location appears less interesting than that for clustering.

Questions for authors

One recent result released by OpenAI claimed to disprove ETH, and if it is true, the lower bound result assuming it will not hold any more. Is there another way to establish a lower bound?

1 comment

We thank the reviewer for the thoughtful comments and the question about ETH.

1. Why study these prediction models for facility location?

The opening-cost/connection-cost trade-off is precisely the feature that distinguishes our setting from fixed-kk clustering.

Knowing the complete reference partition indeed makes the problem easy, but a predicted client partition does not specify which facilities should be opened. The same observation applies to clustering when its reference partition is fully known. Moreover, in the query setting, only a sample of the predicted partition is available. The question is how much imperfect information about that partition suffices to obtain a near-optimal solution.

For UFL, transferring sampling arguments is particularly interesting because subsampling changes the scale of connection costs but does not change the one-time cost of opening a facility. Our analysis handles this interaction explicitly and quantifies the oracle information sufficient to preserve the approximation guarantee.

We also clarify that our model does not require a unique optimal solution. We fix an arbitrary optimum as a reference for interpreting predictions, while allowing other optimal solutions to exist.

In M3, even when the prediction specifies facilities directly, small opening-cost error does not necessarily imply a small connection cost. Our results quantify how such structural prediction errors affect the full UFL objective.

We have made these motivations more explicit in the revised introduction.

2. The recent ETH result and our lower bounds.

Thank you for raising this question. We have revised the lower-bound section and established several new results that do not rely on ETH.

In particular, for M3, we now prove that the coefficient 11 of the false-positive error η+\eta^+ and the leading coefficient 11 of the false-negative term η−log⁡(OPT/η−)\eta^-\log(\mathrm{OPT}/\eta^-) are both optimal. These results hold even when the normalized prediction error tends to zero and almost all optimal facilities are predicted correctly.

We also establish constant-factor hardness for UFL when every optimal cluster contains at most three clients.

These results require only P≠NP\mathrm P\ne\mathrm{NP} for deterministic polynomial-time algorithms, or NP⊈BPP\mathrm{NP}\not\subseteq\mathrm{BPP} for randomized algorithms.

For the stronger near-subexponential oracle-query lower bounds, we have revised the manuscript to state the required quantitative gap assumption for Vertex Cover on 4-regular graphs explicitly, denoted H4\mathsf H_4.

The distinction from the recent ETH result is quantitative. The announced SAT algorithm runs in roughly 2n/log⁡n2^{n/\sqrt{\log n}} time, up to lower-order factors in the exponent. In contrast, the gap assumption needed by our reduction rules out algorithms running in

2O(N1−ζ)2^{O(N^{1-\zeta})}

for every fixed ζ∈(0,1)\zeta\in(0,1), where NN is the number of vertices.

For every such ζ\zeta,

Nlog⁡N≫N1−ζ.\frac{N}{\sqrt{\log N}}\gg N^{1-\zeta}.

Thus, even a comparable speedup for gap Vertex Cover would not contradict the assumption needed here.

The recent ETH result therefore does not by itself invalidate H4\mathsf H_4. Our stronger query lower bounds remain conditional on this explicitly stated assumption. We do not claim that H4\mathsf H_4 follows from ordinary NP-hardness or that it has been established independently.

The new polynomial-time hardness results, including the tight M3 lower bounds, do not depend on H4\mathsf H_4.

We appreciate the reviewer for raising these points, which helped us clarify the motivation for our models and the assumptions underlying our lower bounds.

Reviewer_S7YaOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies offline metric uncapacitated facility location with predictions. Given clients CC, candidate facilities FF, opening costs fi≥0f_i \geq 0, and a metric dd, the objective is to choose a nonempty set S⊆FS \subseteq F minimizing

c(S)=∑i∈Sfi+∑j∈Cmin⁡i∈Sd(i,j).c(S) = \sum_{i\in S} f_i + \sum_{j\in C}\min_{i\in S} d(i,j).

There is no constraint on the number of facilities opened. Write n=∣C∣n=|C| and m=∣F∣m=|F|. Fix an optimal solution S∗={s1∗,…,sk∗}S^*=\{s_1^*,\ldots,s_k^*\}, let OPT=c(S∗)\mathrm{OPT}=c(S^*), and let Ci∗C_i^* contain the clients assigned to si∗s_i^*, using a fixed tie-breaking rule. The paper considers three prediction settings:

\begin{enumerate} \item \textbf{Noisy client labels (M1).} A predictor returns a label Π(j)∈[k]\Pi(j)\in[k] for each client jj. Let Xi={j:Π(j)=i}X_i=\{j:\Pi(j)=i\} be the predicted clusters. After matching the predicted labels with the true clusters, every true cluster is assumed to lose at most an α\alpha-fraction of its clients, and every predicted cluster contains at most an α\alpha-fraction of clients from other clusters, where 0≤α<1/20\leq\alpha<1/2. These errors need not be independent or random. The paper considers both access to all labels and a query model in which one query reveals Π(j)\Pi(j).

Algorithm1 selects the facility minimizing opening plus
connection cost for each predicted cluster $X_i$, and
opens the union of these facilities.
Its approximation ratio is
R(α)=1+4α1−2α,R(\alpha)=1+\frac{4\alpha}{1-2\alpha},
using all $n$ labels.

Algorithm 2 aims to reduce the number of label queries.
It uses a first sample to estimate cluster sizes, then a
second sample to select facilities using empirical connection
costs and opening costs scaled by the estimated cluster sizes.
Theorem~1 claims an $R(\alpha)(1+\varepsilon)$-approximation
with probability at least $1-\delta$, using
Q1=O ⁣(kθmax⁡{1δlog⁡kmε2,log⁡kδ})Q_1 = O\!\left( k\theta \max\left\{ \frac{1}{\delta} \log\frac{km}{\varepsilon^2}, \log\frac{k}{\delta} \right\} \right)
label queries, where
\$
    \theta=\frac{n}{k\min_i|X_i|}.
\$
However, I think the sample guarantee is not correct as stated, see weakness for the counter example.

\item \textbf{Noisy same-cluster queries (M2).}
A query on clients $u,v$ returns a bit predicting whether
they are assigned to the same facility in $S^*$.
Each distinct pair's answer is independently incorrect with
probability at most $\alpha<1/2$. Answers are persistent:
repeating a query returns the same bit rather than a fresh
noisy observation.

Algorithm 3 proposes to sample clients, recover their
underlying partition using an existing noisy-query clustering
algorithm, and choose one facility per recovered cluster.
Facility selection again uses sampled connection costs and
opening costs scaled by estimated full cluster sizes.

Theorem 2 claims a $(1+\varepsilon)$-approximation with
probability at least $1-\delta$, using
Q2=O~ ⁣(max⁡{k2θ(1−2α)4,kθδlog⁡kmε2,kθlog⁡kδ})Q_2 = \widetilde{O}\!\left( \max\left\{ \frac{k^2\theta}{(1-2\alpha)^4}, \frac{k\theta}{\delta} \log\frac{km}{\varepsilon^2}, k\theta\log\frac{k}{\delta} \right\} \right)
pairwise queries. Here
\$
    \theta=\frac{n}{k\min_i|C_i^*|},
\$
so the imbalance parameter concerns the true clusters,
unlike in M1. These approximation and query guarantees are not established
by the presented algorithm and analysis either, as discussed below.

\item \textbf{A predicted facility set (M3).}
The prediction is a set $P\subseteq F$. Its error is
measured by
η+=∑i∈P∖S∗fi,η−=∑i∈S∗∖Pfi.\eta^+ = \sum_{i\in P\setminus S^*}f_i, \qquad \eta^- = \sum_{i\in S^*\setminus P}f_i.
Algorithm 4 sets the opening costs of facilities in $P$
to zero and runs a classical
$(\lambda_f,\lambda_c)$-bifactor approximation, with
separate factors for opening and connection costs.
If that algorithm returns $S'$, the final output is
$P\cup S'$, evaluated using the original opening costs.

Theorem 3 gives
E[c(P∪S′)]≤λc OPT+η++(λf−λc)η−,\mathbb{E}[c(P\cup S')] \leq \lambda_c\,\mathrm{OPT} + \eta^+ + (\lambda_f-\lambda_c)\eta^-,
where the expectation is needed when the underlying
bifactor algorithm provides an expected guarantee.
Using the classical choice
$\lambda_f=\lambda$ and
$\lambda_c=1+2e^{-\lambda}$, for
$\lambda\geq1.6774$, gives expected approximation ratio
1+2e−λ+η++(λ−1−2e−λ)η−OPT.1+2e^{-\lambda} + \frac{ \eta^+ +(\lambda-1-2e^{-\lambda})\eta^- }{\mathrm{OPT}}.

\end{enumerate}

Critical strengths
Critical weaknesses

I have concerns about both the value of predictions in the proposed settings and the correctness of the query-efficient results.

The facility-set model (M3) illustrates the concern most clearly. Given a nonempty predicted solution PP, one can evaluate its true cost, run a classical algorithm BB with expected approximation ratio ρ\rho, and return the cheaper solution. This immediately gives

E[c(H)]≤min⁡{c(P),ρ OPT},\mathbb{E}[c(H)] \leq \min\{c(P),\rho\,\mathrm{OPT}\},

and hence consistency, robustness, and smoothness in the objective-value error of PP.

The algorithmic ideas are largely straightforward extensions of existing methods: M1 selects the best facility for each predicted cluster, essentially following the prediction; M2 attempts to reconstruct the partition of sampled clients using an existing noisy-query routine and then applies sampled facility selection; and M3 modifies opening costs before invoking a classical bifactor approximation.

For M3, the remaining guarantee uses an error measure based solely on opening costs, adopted from the weighted subset-selection framework of Antoniadis et al.\ (2025). The paper provides little UFL-specific motivation for this choice, which omits the connection-cost component of the objective. Although the resulting structural-error bound is not implied by the best-of-two baseline, I find the additional contribution insufficiently motivated. Theorem~5 does provide a lower bound, but it does not match the coefficients in the upper bound or establish tightness when normalized prediction error tends to zero.

The query-efficient results are more interesting, but their current arguments do not go through. In particular, the query-efficient guarantees in both M1 and M2 rely on Lemma8, which is false as stated. A constant-relative-error cluster-size estimate biases the opening-cost term; increasing the second sample does not remove this bias. This issue invalidates the claimed guarantee of Algorithm2, even with perfect predictions.

For a concrete counterexample, let s=50,000s=50{,}000. Take a tree with facilities a,b,ca,b,c, edges abab and acac of lengths 11 and 100100, and ss distinct client leaves of length 10−410^{-4} attached to each of aa and cc. Set fa=49,500f_a=49{,}500 and fb=fc=50f_b=f_c=50. The unique optimum {a,c}\{a,c\} costs 49,56049{,}560, whereas {b,c}\{b,c\} costs 50,110>1.01 OPT50{,}110>1.01\,\mathrm{OPT}.

Give Algorithm 2 perfect labels and set ε=0.01\varepsilon=0.01 and δ=0.1\delta=0.1. Here k=2k=2 and θ=1\theta=1. Taking logarithms to be natural and rounding sample sizes upward gives M1=259M_1=259 and M2=95,059M_2=95{,}059. If the first sample contains 1≤T≤1281\leq T\leq128 clients from the aa-cluster, its size estimate satisfies

n^a=100,000T259<49,450=fa−fb.\widehat n_a = \frac{100{,}000T}{259} < 49{,}450 = f_a-f_b.

For any nonempty second-stage sample UaU_a from this cluster, the empirical score of aa minus that of bb is

∣Ua∣(−1+fa−fbn^a)>0.|U_a| \left( -1+\frac{f_a-f_b}{\widehat n_a} \right)>0.

Thus, bb is preferred to aa; facility cc has the same opening cost as bb and is farther from these clients. The other cluster selects cc, and M2>sM_2>s ensures that both clusters appear in the second sample. The adverse first-sample event has probability

Pr⁡(1≤T≤128)=∑t=1128(st)(s259−t)(2s259)≈0.4505,\Pr(1\leq T\leq128) = \frac{ \sum_{t=1}^{128} \binom{s}{t}\binom{s}{259-t} }{ \binom{2s}{259} } \approx 0.4505,

exceeding the permitted failure probability 0.10.1. This contradicts Theorem 1's guarantee for Algorithm 2.

For M2, Algorithm 3 additionally uses cluster labels that its pairwise oracle does not supply. Its query accounting also counts sampled clients without justifying the number of pairwise queries needed by the recovery routine. Applying the paper's own Lemma 6 to M2M_2 clients supplies an upper bound of

O ⁣(M2klog⁡M2(1−2α)4)O\!\left( \frac{M_2k\log M_2}{(1-2\alpha)^4} \right)

for the recovery call; it does not establish the smaller query count used in Theorem 2, which reports only M1+M2M_1+M_2. The approximation analysis also relies on the false Lemma 8.

\medskip \noindent\textbf{Recommendation: Reject.} The remaining approximation contributions appear incremental, while the potentially more substantial query-efficient results contain substantive correctness problems. I therefore recommend reject.

Questions for authors

Please feel free to correct me re the correctness issue

2 comments

We thank the reviewer for the careful assessment. We have revised Algorithms 2 and 3 and their analyses, and added new results for M3. The changes are highlighted in blue in the revised manuscript.

1. M1: Correctness of the sampling algorithm.

Thank you for the detailed counterexample. You are correct: the original Algorithm 2 does not satisfy its claimed guarantee. We have corrected both the lemma and the algorithm.

The corrected estimated-size lemma requires

∣∣X∣x−1∣≤ε2(2+ε)\left|\frac{|X|}{x}-1\right|\leq\frac{\varepsilon}{2(2+\varepsilon)}

and explicitly bounds the resulting opening-cost perturbation.

The revised Algorithm 2 avoids cluster-size estimation altogether. It draws one uniform sample UU of size mm and minimizes

fv+nm∑j∈U∩Xid(j,v)f_v+\frac{n}{m}\sum_{j\in U\cap X_i}d(j,v)

for each predicted cluster XiX_i. The proof controls empirical differences between facility costs and transfers these comparisons to the true clusters through Lemma A.1, retaining the opening-cost difference throughout.

This establishes the claimed

1+2α1−2α(1+ε)\frac{1+2\alpha}{1-2\alpha}(1+\varepsilon)

approximation, with the revised label-query bound

O(kθ1ε2(1−α)2(1−2α)2log⁡k∣F∣δ),O\left(\frac{k\theta_1}{\varepsilon^2(1-\alpha)^2(1-2\alpha)^2}\log\frac{k|F|}{\delta}\right),

capped at nn. The corrected arguments appear in Appendix A.

2. M2: Unavailable labels and query accounting.

The reviewer also correctly points out two issues with the original Algorithm 3: the pairwise oracle does not supply the labels used in its first stage, and the number of sampled clients is not the number of pairwise queries.

We have replaced that algorithm. The revised construction recovers a pilot sample using a signed SDP, then classifies the remaining optimization sample using fresh pairs to representatives of the recovered pilot parts.

All labels are obtained through pairwise queries, and all queried pairs are counted. Writing γ=1−2α\gamma=1-2\alpha, the new query bound is

O~(k4θ24γ4+k2θ2ε2γ2).\widetilde O\left(\frac{k^4\theta_2^4}{\gamma^4}+\frac{k^2\theta_2}{\varepsilon^2\gamma^2}\right).

The revised theorem requires the pilot-feasibility condition

n≥C(kθ2)2γ−2log⁡32nk∣F∣δ.n\geq C(k\theta_2)^2\gamma^{-2}\log\frac{32nk|F|}{\delta}.

This condition and the new query bound are stated explicitly in Theorem 2. Appendix B provides the SDP recovery analysis, rounding guarantee, fresh-pair classification argument, and facility-cost analysis.

3. M3: The best-of-two baseline and tight lower bounds.

The best-of-two approach suggested by the reviewer is a natural baseline, and we have added this comparison to the revised manuscript, together with a best-of-three guarantee.

Our main distinction concerns how prediction error is measured. The prediction specifies facility-opening decisions, while the metric and connection costs are already available to the algorithm. Our guarantee is

E[c(S^)]≤(1+2e−λ)OPT+η++(λ−1−2e−λ)η−,\mathbb E[c(\widehat S)]\leq(1+2e^{-\lambda})\mathrm{OPT}+\eta^++(\lambda-1-2e^{-\lambda})\eta^-,

for λ≥1.6774\lambda\geq1.6774.

A larger λ\lambda brings the coefficient of OPT\mathrm{OPT} closer to one, at the expense of greater sensitivity to false negatives.

In particular, η−\eta^- can be small even when the predicted solution has a very large connection cost. In this case, the best-of-two bound may provide only the classical approximation guarantee, whereas our structural-error bound can give a substantially stronger guarantee. We have included an explicit example illustrating this difference.

We have also strengthened the lower bounds to address the question of tightness when prediction errors are small.

We now prove that the coefficient 11 of η+\eta^+ and the leading coefficient 11 of η−log⁡(OPT/η−)\eta^-\log(\mathrm{OPT}/\eta^-) are both optimal. These results hold even when the corresponding normalized prediction error tends to zero and almost all optimal facilities are predicted correctly.

For deterministic polynomial-time algorithms, the lower bounds hold under P≠NP\mathrm P\ne\mathrm{NP}; for randomized algorithms, under NP⊈BPP\mathrm{NP}\not\subseteq\mathrm{BPP}. These lower bounds match the leading coefficients of our optimized upper bound in the small-error regime, providing a tight characterization of the dependence on prediction errors in this setting.

Thank you again for identifying the issues in M1 and M2. Your comments have helped us improve the correctness and presentation of the paper, and we would appreciate any further feedback on the revised results.

I appreciate the authors efforts in fixing the mistakes. Still, I have concerns about the relevance of the results and don't have enough confidence that the rest of the paper is correct. I am going to keep my score at 1.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.