- 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 , and clients , each facility has an associated opening cost. The goal is output a subset of facilities 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 with facilities.)
-
M1: In this model predicted label is given to each client from a set . After relabeling (a map from to ), the predicted clusters are required to have precision and recall of wrt . The basic algorithm groups clients by their predicted label and for each cluster computes the facility that minimizes the cost. They obtain a approximation for . Another algorithm that must query the predicted labels is similar, results in another 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 , 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
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.
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 k-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+mn∑j∈U∩Xid(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 v with a reference facility q and use ∣d(j,v)−d(j,q)∣≤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 X and reference cluster Y have two-sided overlap at least 1−α, and
cost(X,p)−cost(X,q)≤ξ∣X∣d(p,q),
then cost(Y,p)≤(1+β)/(1−β)cost(Y,q), where β=2α+ξ/(1−α). The opening-cost difference is preserved in this transfer. Combining the two lemmas yields the (1+2α)/(1−2α)⋅(1+ε) 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≤α. 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 (2b)+(m−b)kr queries, and explicitly state the pilot-feasibility requirement b≤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)η−.
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.