Online Rounding and Learning Augmented Algorithms for Facility Location
Authors: Silvio Lattanzi
Debmalya Panigrahi
Ola Svensson
Venue: ICLR 2026 Poster (2026)
Keywords: Learning Augmented Algorithms
Clustering
Facility Location
Primary area: learning theory
TL;DR: New online rounding and learning augmented algorithms for facility location

Abstract: Facility Location is a fundamental problem in clustering and unsupervised learning. Recently, significant attention has been given to studying this problem in the classical online setting enhanced with machine learning advice. While (almost) tight bounds exist for the fractional version of the problem, the integral version remains less understood, with only weaker results available. In this paper, we address this gap by presenting the first online rounding algorithms for the facility location problem, and by showing their applications to online facility location with machine learning advice.

Published as a conference paper at ICLR 2026
ONLINE ROUNDING AND LEARNING AUGMENTED AL- GORITHMS FOR FACILITY LOCATION
Silvio Lattanzi
Debmalya Panigrahi
Ola Svensson
Google Research
Duke University
EPFL
Barcelona, Spain
Durham, United States
Lausanne, Switzerland ola. wwwnsson@epfl..cmm
silviol@google.co
debma 1 ya@cs. duke. edu
ABSTRACT
Facility Location is fundamental problem in clustering and unsupervised learning. Recently, significant attention has been given to studying this problem in the classical online setting enhanced with machine learning advice. While (almost) tight bounds exist for the fractional version of the problem, the integral version remains less understood, with only weaker results available. In this paper, we address this gap by presenting the first online rounding algorithms for the facility location problem, and by showing their applications to online facility location with machine learning advice. Beyond its implications for the learning augmented setting, our results also show that the hardness of the classic online facility location problem lies in computing good fractional solution and not in rounding it.
INTRODUCTION
Clustering is a central problem in unsupervised learning. In recent years, to capture the evolving nature of real world data, there has been increased interest in clustering problems in the online setting, where the set of points that have to be clustered is not known in advance and is revealed to the algorithm over time Meyerson (2001); Alon et al. (2006); Fotakis (201 1); Lattanzi and Vassilvitskii (2017); Almanza et al. (2021); Cohen-Addad et al. )) Fotakis et al. (2021b); Lattanzi et al. (2021); Anand et al. (2022); Cohen-Addat et al. (2022). This increased interest reflects the growing importance of performing learning tasks in uncertain and dynamically changing environments. To mitigate the negative impact of the uncertainty on algorithmic performance, new paradigm using machine-learned predictions has rapidly gained traction in the last few years Purohit et al. (2018); Antoniadis et al. (2020); Bamas et al. (2020); Lattanzi al. (2020); Wei and Zhang (2020); Im et al. (2021); Lykouris and Vassilvitskii (2021); Chen et al. (2022); Mitzenmacher and Vassilvitskii (2022); Bai and Coester (2023). The basic tenet of this framework to simultaneously ensure that the algorithm is able to exploit good predictions about the future (called consistency) while being minimally affected by bad ones (called robustness), although it is unable to distinguish the good from algorithms for the classical facility
the bad predictions presented to it. In this paper, we present location problem in the online setting augmented with machine-leamen predictions. These results are derived via novel online rounding algorithms of fractional solutions, which may be of independent interest.
In clustering problems, the goal is partition (or cluster) a of data points (called clients) into designated groups (or clusters) while optimizing desired objective. One of the most popular is the k-median problem, which asks select cluster centers such that the sum of distances of the clients from their nearest cluster centers is minimized. The condition that only A centers can be chosen can be rather constraining, particularly in the online setting where it renders the problem uninteresting because the algorithm fails to remain competitive after it has opened all & centers.
natural and well-studied (Lagrangian) relaxation of k-median is the facility location problem. where an arbitrary number of centers (called facilities) can be opened but each open facility adds an
Supported part by NSF grants CCF-2329230 and 195-1955703.
'Supported by the Swiss State Secretariat for Education, Research and Innovation (SERT) under contract number MB22.00054.

---

Published as a conference paper at ICLR 2026
opening cost to the objective. The online facility location problem where clients arrive time was introduced by Meyerson Meyerson (2001), and has since been studied extensively Anagnostopoulos et al. (2004); Fotakis (2007; 2008: 2011) 1). The advantage of this setting is that it produces stable clusters that can be used in downstream tasks, notably as input to machine learning models, whereas changes to the clustering would incur substantial overhead. In recent years, interest has grown in obtaining Searning-augmene
algorithms for this problem, where machine-learned suggestions about the clustering solution are incorporated into the decision-making of the algorithm Almanza al. (2021); Jiang et al. (2022); Fotakis et al. (2021a): Anand et al. (2022). This has led to almost tight bounds for fractional versions of this problem, while the integral version remains less understood, especially in the presence of multiple advice. In this paper, we address this gap by presenting the first online rounding algorithm for facility location, and show its applications to learning-augmentee versions of the problem.
Our Contributions. We present two new online rounding algorithms for the facility location problem. Both algorithms take input fractional solution and produce an integral solution in the online setting. To the best of our knowledge, these are the first two online rounding algorithms for the metric facility location problem. This work introduces novel techniques that heavily exploit the problem's 's underlying metric structure, contributing to the growing literature on online rounding algorithms. We believe these techniques are also of interest for broader range of clustering problems.
Our first algorithm is for the uniform version, where all facilities have the same opening cost. In this case, give a deterministic online rounding algorithm that produces an integral solution whose cost is only a constant times that of the fractional solution input to it. Paired with prior results for the fractional problem, we obtain new algorithms for the integral facility location problem with machine learning advice that matches the almost tight results, which were previously only known for the fractional version.
Our second algorithm is for the non-uni uniform problem with arbitrary facility opening costs. For this more general problem, we give an online rounding algorithm that is randomized and loses factor of Ollog log A) in expectation compared to its fractional input, where A is the aspect ratio of the underlying metric space. We remark that, by standard techniques (see Appendix E), the upper bound (log log A) may be replaced by Ollog log n)), where is the number of clients in the instance. As in the uniform case, this algorithm can be paired with existing algorithms for the corresponding fractional problem and yields nearly optimal competitive algorithm for the online problem.
As an application of our rounding algorithms, we obtain the first integral algorithm for online facility location in the multiple predictions setting Almanza et al. (2021); Anand et al. (2022). The consistency bounds that we obtain are tight up to lower-order terms, thereby bridging fractional and integral results for this problem. Simultaneously, we also obtain tight robustness bounds for the -aggentdd setting by using a combiner algorithm that obtains the better of the solutions between our algorithm and online facility location without predictions.
All our rounding algorithms run in polynomial time in the number of revealed clients; a detailed running time analysis is provided in Appendix F.
Other Related Work. The two most related works are Almanza et al. (2021); Anand et al. (2022). The first paper studied the aagnennee facility location problem in the uniform case. Their integral algorithm has a cost overhead of Olog log n1) compared to the best fractional solution, and works in the simplified setting where all the predictions are presented before any client arrives. In comparison, we improve the cost overhead to (11) and no longer require the predictions to be given upfront. The second paper studied online covering problems with multiple machine learning advice. They provide several interesting results in this setting and in particular an online fractional algorithm to the learning- augmentd facility location problem. Our work bridges this fractional result and the integral facility location problem. We also note that there is prior work on online facility location with a single machine learning advice Azar et al. (2022); Fotakis et al. (2025), or from a mechanism design perspective Balkanski et al. (2024). The results in these papers do not have any implication for the multiple predictions settings of the current paper, and are obtained using very different techniques.
More broadly, there has been significant recent interest in online rounding algorithms, especially for matching problems Buchbinder et al. (2023); Naor et al. (2025). In addition to its application to Barning-auugenter algorithms, our work adds to this portfolio of online rounding algorithms, specifically extending it beyond packing to covering problems. Our techniques differ from previous
2

---

Published as a conference paper at ICLR 2026
work in that they structural properties of the underlying metric space to define rounding solutions, both using deterministic and randomized tools. Indeed, this in sharp contrast to prior work on online rounding for facility location in non-metric settings Alon et al. (2006); Bienkowski et al. (2020). In these papers, the rounding algorithms must incur a logarithmic loss (being basically identical to the set cover problem) while we incur sub-logarithmic loss by exploiting metrie properties.
Organization. We formally define our problem and state our results in Section 2. In Section 3, we present the deterministic rounding algorithm for the uniform setting. In Section 4, we present the randomized rounding algorithm for the (general) non-uniform case. In Section 5, we give applications facility location
of these rounding algorithms to obtain new results for the mouriing-uugenter problem. In Appendix D, we present a lower bound showing that our analysis of the randomized rounding algorithm for the non-uniform setting (asymptotically) tight. Finally, in Appendix we provide a running time analysis of our rounding methods.
2
PRELIMINARIES
Online Facility Location. The classic online facility location problem is defined metric space (V, d), where V is a set of vertices and d the distance function between vertex pairs satisfying the standard properties of metric space: (i) "Non-negativity d(u, v) 2 0 for all u, V with d(v,v) = 0 for all v E V, (ii) (Symmetryy d(u, v) = d(v, u) for all u, v E V, and (iii) (Triangle Inequality) d(u, v) d(v,, w) 2 d(u, w) for all u, v, W...
The metric space (V.d) is revealed online to the algorithm: in each online step t, a new vertex e Vi is revealed along with (i) its distance all vertices revealed in previous steps, and (ii) its (non-negative) facility opening cost c(vz). If the opening cost is uniform across all vertices, then it is uniform instance, otherwise it is non-uniform instance. By scaling, all opening costs are in the uniform case.
We denote the set of vertices revealed the first steps Vz. In step t, the online algorithm's 's solution comprises a subset of vertices in Vi where facilities are opened by the algorithm: we denote this set Fú. The sets F2 must be monotone over time, i.e., an open facility cannot be closed: F1 C F2 c... S Ft- The connection cost of a vertex E V, is its distance to the closest open facility. Collectively, the cost of the solution the sum of the opening costs of the facilities and the connection costs of all vertices, i.e., alg,- EnER, c(u) + Enev, min.eF, d(u, v).
Let opt, denote the cost of an optimal solution on the instance (V,, d). Then, the competitive ratio of the online algorithm is defined as: max, alg,/ Moreover, if the algorithm randomized, the competitive ratio is max, B //alg,]/opt, where the expectation is over the random choices of the algorithm.
Fractional solution and ML-advice. To define valid fractional solution, it would be convenient to first write a (standard) LP relaxation of the problem. The following is the LP at step t:
minimize
Σ VEV/
c(u) V + Σ
Σ
d(u, v) zn such that
WVV VEV2
Σ V
x uu
=
Vu E V.
Ve Vi
Vu, V,
The online fractional solution in step a feasible solution to this I.P. Moreover, the variables v that represent the fraction of the facility at vertex that is open time are non-decreasing over time: v. < y8 s... for all v. We will refer to the value of yf as the fractional mass at vertex v at time t.
Note that the values of v completely specify the fractional solution even without explicitly defining x This is because the optimal values of the z variables is given as follows: for each client Vi, order the vertices in Vi in non-decreasing distance from u (breaking ties arbitrarily), and select the minimal prefix of this order such that the total fractional mass in this prefix is at least 1. Now, assign s'i = v for all facilities in this prefix, except possibly for the last one. For this last
3

---

Published as a conference paper at ICLR 2026
vertex, the value of zgee is such that sum of dye over all the facilities in the prefix is 1. The value of Eue for all vertices outside this prefix is O.
In the Cearning-augmentee facility location problem, whenever new vertex arrives, one also receives & feasible suggestions (predictions) yo (v.(1),.... (k) for the value of ye. We consider the k suggestions at each step as collection (or bag) of predictions, disregarding any association with specific predictors. Our objective is to achieve performance comparable to the best suggestion in each step, i.e., we seek the minimum-cost solution that is consistent with at least one suggestion at every stage. Formally,
dynamic, = min Σ c(u) Do + + BEY NEVi
Σ
d(u, v) x'..
NEV, NEV.
where y = {ū= Vo E V1 3i E (1,00 vo())} and shw are defined using the values of ÿ as described above.
It is interesting to note that this model of predictions generalizes other natural types of predictions. E.g., if the predictions specify opening a facility at a vertex when it arrives or even at the very outset Almanza et al. (2021), it can be simulated by setting y,, 1 in our prediction model. In fact, our prediction model captures the very natural setting where the variable y, represents the probability that facility is opened vertex v.
We also note that our algorithm consider the possibility to open previously specified facilities as long the assignment is online. This is standard in the literature. In fact, in the traditional online model for the facility location problem, introduced by Meyerson (2001), for non-uniform facility location(this is specified in the first paragraph of Section 3 in Meyerson (2001)) the facility locations are known before the clients arrive online, the demands are specified online and the assignments and the opening are decided online (in particular any facility location can be opened any time and this is necessary in this setting). Furthermore, in Almanza et al. (2021), in the non- non-uniform case, the set of suggested facilities is specified in advance and facilities can be opened in these specified locations.
In the augmenttd facility location problem, we aim to return an integral solution (i.e. a solution where all the y variables have integral value) such that its cost bounded by min{a dynamic,, 3 ) for and B as small as possible. From lower-bounds in previous works Al- manza et al. (2021); Anand al. (2022), we know that 2 (2008).
log k and that S
lngt Fotakis log
log log
With the above notation, we can state the implication of our rounding algorithms more formally for the aannnnnee problems. First, we study the uniform setting where all the facilities have the same opening cost. In this setting, our rounding algorithm implies a deterministic algorithm that obtains a O(min<log(k: + 1) dynamic,, log log opt, Japproxiixi,,,nonnn improving previous work in the area. Second, we use our non con-uniform facility rounding algorithm to obtain the first Baaming-augmentn
log
algorithm for the non-uniform facility location problem. Our algorithm returns a Olog log min (log + 1) dynamic, log log
that, by standard techniques (see Appendix E), the upper bound O(log log A) may be replaced by Oloog log n)). Both results start from the fractional solution built for the Saaning-auugmettn facility location problem designed in previous work Anand et al. (2022) and use our online rounding algorithms to obtain the final integral results.
log opt,)) "ol.))-approximaiionnne
Additional notation. Consider the metric space (V,, d) at time t. The ball centered at some vertex E Vj with radius R 2 in this metric space denoted B' B'(v, R): B' (v, R) = {u E V d(u, v) S R). For any set of vertices S C V,, the total fractional mass on the vertices of S at time t is denoted (S):: (S) = Eves y'y. Clearly, y (S) is also non-decrgaging over time. In particular, we will often consider the total fractional mass at time in a ball = B¹ (v. r); this is denoted y'
--Consistent Rounding, Consider a fractional solution y' (vÉ. Vt) (recall from above that y' is sufficient to define a solution). Now, suppose we round this fractional solution to produce an integer solution F, C Vi. We say that F, is ccoosistentt with y' if the following property holds:
(y- (--Conniistecy)) For any ball B = B' (v. R) centered at a vertex v E V2 and with radius R, y' (B) 2 1/2, then there an open facility in F, that is within distance RR of v.
4

---

Published as a conference paper at ICLR 2026
We show that the y-consistency property implies that the connection costs of the fractional and integral solutions are related.
Lemma 1. If an integral solution Fe is "y-consistent with fractional solution y', then the total connection cost of all the clients Ve in the integer solution is at most 27 times that in the fractional solution. In notation,
E min d(u, S 27
ΣE d(u, x
NEV. VER.
REV for any x' such that (y", x²) is feasible for the LP given above.
Proof. Consider client at vertex u that arrives at time Suppose its fractional connection cost is 3, i.e., Ever d(u, v) = B where Evey Fye = 1 and x' I y for all v E Vi. Then, EveB(u. vi 2 ((. tue 2 1/2. Note that 7-consistency ensures that there is at least one (2) facility at distance 2 from after the processing at time t. It follows that the connection cost of client u in the integer solution is at most 2y,3.
Our goal is to obtain >-cometitive solutions so that the total connection cost can be bounded immediately by Lemma 1. So, our analysis will comprise two parts: first, obtain an explicit bound on the facility opening cost Ever, <(v) of the integral solution against the opening cost of the fractional solution, Enev, <v)) yo: and second, establish y-competitiveness of the integral solution with respect to the fractional solution for a suitable value of 7.
DETERMINISTIC ROUNDING ALGORITHM FOR UNIFORM OPENING COSTS
In this section we present our deterministic online rounding algorithm for the uniform facility case. This algorithm combined with the fractional algorithm in Anand et al. (2022) will imply our result for learning augmmente facility location as we will show in Section 5.
We start by stating the main result of this section.
Theorem 2. There exists an online algorithm that rounds a fractional solution of uniform facility location online and the cost of the returned integral solution O(x), where a denotes the cost of the fractional solution.
The Algorithm. The main idea behind the algorithm is to guarantee that at any point in time the algorithm is 4-consistent. In order to do so if at time & ball ('vr, R) has total fractional mass (B) 2 1/2 and has the closest open facility at a distance 2 4R we open a facility at v. While this guarantees 4-consistency, it can lead to excessive facility openings. To mitigate this, additional facilities are opened. Roughly, if there is a ball B' B'(urr) r) with total fractional mass in the ball y' (B) 2 1/4 that intersects ('.v. Rt) and such that the closest open facility to is at a distance 2 3r we open also a facility at u. In addition, we do this an additional time by considering balls Bt (w, p) with total fractional mass in the ball y (B) 2 7/8, intersecting with 3 (u, r) and with closest open facility to w is at a distance > 2p and by opening a facility in such w. Interestingly, by opening these additional facilities we can show that the number of open facility is bounded and by combining this with the fact that the algorithm is 4-consistent we obtain the theorem.
Roughly speaking the algorithm uses three levels covering scheme. Level-1 (Condition A balls): The algorithm identifies a large primary region, B(v R), containing significant fractional mass (z 1/2) that lacks nearby facilities (distance 4R). It commits to opening facility here. Level-2 (Condition B balls): To ensure dense, off-center subsets of this demand are adequately served, the algorithm searches for smaller overlapping balls, (u,, r). with mass of 2 1/1 that are also poorly served (distance > 3r). Level-3 (Condition C balls): Finally, it recursively checks for even smaller, isolated pockets of mass (2 1/8) overlapping the Level-2 ball. Crucially, to prevent over-opening, these Level-3 balls are proven to be mutually disjoint, meaning Level-2 ball will spawn at most 3 Level-3 facilities.
To define the algorithm, we start to formalize the three conditions discussed above:
A ball B (v, R) is said satisfy Condition A at time if the following holds: the total fractional mass in the ball (B) 2 1/2
the closest open facility is at distance > 4R.
5

---

Published as a conference paper at ICLR 2026
Figure I: Green balls are at level-1, red balls are at level-2, blue balls are at level-3. Level-3 balls associated with the same level-2 balls are disjoint and are at most 3. Level-2 and level-1 balls can overlap but any new ball is associated with some new additional fractional mass. This allows us to bound the number of level-2 and level-1 balls.
A ball B B'(u,) ) is said satisfy Condition B time t if the following holds: the total fractional mass in the ball (B) 2 1/4
the closest open facility is a distance > 3r.
A ball B (w,,, p) is said satisfy Condition C at time if the following holds:
- the total fractional mass in the ball y (B) 2 1/8
the closest open facility is at distance 2p.
We use the above conditions to define the online algorithm. In the description below, we define the algorithmic steps at some time t. For the purpose of analysis, it would be convenient to think of time continuous, although the actual implementation of the algorithm skipping over times where the online algorithm does not make any updates.
be easily discretized by
When client arrives, the algorithm first updates the fractional solution, then rounds it based on Algorithm 1, and finally connects the client to the closest open facility.
Algorithm 1: The Deterministic Online Rounding Algorithm for Uniform Facility Location while a hall (e, R) satisfying condition do
Let (v, R) be ball of minimum radius satisfying the condition A. while a ball B(u, r) for some r S R/3 satisfying condition s.t. B(u,r) B(u, R) + 0 do
Let Bu,, r) be a ball of minimum radius satisfying the condition and intersecting
Blv R);
while a ball B(w, p) for some S satisfying condition s.l.
B(w, p) n B(u,r) # 0 do
Let B(w, p) be ball of minimum radius satisfying the condition C and intersecting r); Open a facility at w;
Open a facility at u;
Open a facility at
Analysis. First, we bound the facility cost, namely show that the number of facilities opened by the algorithm at most a constant times the final value the fractional solution Σ, ye-
We call the ball selected in the outer loop level-1 ball and the respective facility level-1 1 facility, the one selected in the second loop level-2 ball and level-2 facility and the one selected in the innermost loop level-3. In Figure 1, show graphically the interaction between ball at different levels. Note that a ball at level-1 only open single in the outer loop, a ball at level-2 open single facility at level-2 but possibly multiple facilities at level-3. So in our proof we first bound the number of facilities opened in level-3. Then we show how to bound the number of level-1 and level-2 facilities. To do this, we first need establish disjointness of the level-3 balls associated with level-2 ball.
Lemma 3. The level-3 balls associated with level-2 ball B(u, r) are mutually disjoint.

---

Published as a conference paper at ICLR 2026
Proof. Suppose not; let (uw, p) and B(w', p²) overlap. Without loss of generality, suppose p p.. Then, the algorithm processes (( p) before B(w', ,'). At the end of the processing for B(w, p). the algorithm opens level-3 facility w. Since ((w, p) and B(w', overlap, we have d(w, w²) S + p'. Therefore, there is an open facility at distance S + o from w'. Yet, B(w', p¹) satisfies condition C; this implies p ++// of > 2p/, i.e., P p'. This is contradiction.
Lemma 4. The total number of level-3 facilities opened by a (level-2) ball B(u,r) r) is at most 3.
Proof. Suppose B(u,r) r) opens 2 4 level-3 facilities. Since the level-3 balls corresponding to these facilities are mutually disjoint (by Lemma 3). it follows that the total fractional mass in these level-3 balls is at least 4 1/8 = 1/2. Now, note that the ball (u, 2r) contains all these level-3 balls; hence, this ball also has fractional mass at least 1/2. The radius of this ball is 2r < 2R/3 < R. Since this minimum radius ball satisfying
ball has a smaller radius than (u, R) but B (,, R) was chosen condition A, it must be the case that (uu, 2r) does not satisfy condition A. Since y (B(Bu, 2r)) 2 1/2, the only way it can fail satisfy condition A is if there is an open facility at distance I 8r from u. But, since the balls (lv, R) and B(u, r) overlap, d(v, u) S. R + r. Thus, v has an open facility at distance at most 8r + + + r) S 88/33 + (R+ + R/3) S 4R. This contradicts the fact that the ball Buv R) satisfies condition A.
Next, we bound the number of level-1 and level-2 facilities. The arguments for these two cases are quite similar. We start by defining predecessors for level-1 and level-2 facilities. Consider a level-1 facility at vertex opened by level-1 ball B(v R) at time t. We call a level-1 facility at some vertex e' the predecessor of the level-1 facility at if the following holds:
-The level-1 facility at v' was opened before the level-1 facility a.
-The level-1 ball (vu, R²) that opened the level-1 facility at v' overlaps with the level-1 I ball B(u, R).
The level-1 balls corresponding to the level-1 facilities opened after o' and before do not overlap with the level-1 ball B(v RR)
Lemma 5. Consider a level-1 facility opened by a ball Biu, R) at time I. Let the predecessor of this level-1 facility at be a level-1 facility at of that was opened by the level-1 ball B(y', R') at time t' < t. Then,
(B(U,, RI)) - (B(v, R)), 1/4
Proof. Since the balls B(u, R) and B(v', R') overlap, we have d(v, 21) R R'. But, note that the ball Bvv, R) satisfied condition A at time f, i.e. there was no open facility within a distance of 4R of v at time t. In particular, this implies that the facility at o' is also at a distance > 4R from v, namely d(v, e'), > 4R. It follows that R + R' > 4R, ie., R' > 3R.
Suppose the lemma is false, i.e., (B(,, R)) - - (B(u, R)) < 1/4. Since y' BB((, R)) 2 1/2, it follows that y (B(v, R)) > 1/4. Since the processing of B(v,, RR) did not open a facility at v, must be that Buv R) failed condition at the end of this processing. Since yf (B(r, R)) > 1/4, the only way this can happen is if there was a facility open at distance S 3R from at the end of the processing for Buv', Rt).. But, this contradicts the fact that B(v, R) satisfied condition A at time t.
The definition of the predecessor of level-2 facility is similar to that for level-1 facilities. Consider a level-2 facility at vertex u opened by level-2 ball B(u, r) at time t. We call a level-2 facility at some vertex u' the predecessor of the level-2 facility at u if the following holds:
The level-2 facility at u' was opened before the level-2 facility at u.
The level-2 ball Bu'' r') that opened the level-2 facility at u' overlaps with the level-2 ball B(u, r). - -The level-2 balls corresponding to the level-2 facilities opened after u' and before u do not overlap with the level-2 ball (u,
Now, using the same proof strategy of Lemma 5, one can show that the overlap between level-2 ball bounded. Here we present the statement of the Lemma and defer the proof Appendix A
Lemma 6. Consider a level-2 facility opened by ball B(u, r)) at time t. Let the predecessor of this level-2 facility at u be a level-2 facility at ue that was opened by the level-2 ball B(u', r') at time t < t. Then,
y' y'((Bu,)) r)) v6 (B(u,r)) 2 1/s.
7

---

Published as a conference paper at ICLR 2026
We now ready bound the facility cost:
Theorem The number of facilities opened by the rounding algorithm is at most 36 Ev yo. where Yo is the final value of the fractional solution for vertex v.
Proof. We charge a level-1 facility opened by a level-1 ball Buu R) the gain in fractional mass (B(v, R)) after time t' until time i, where t' denotes the time when the predecessor of the facility at v was opened. This charging only loses a factor of 4 by Lemma
We charge the level-2 facility and the level-3 facilities opened by level-2 ball B(u, r) to the gain in fractional mass y (u, r)) after time 1' until time I, where I' denotes the time when the predecessor of the facility at was opened. The charging of the level-2 facility only loses factor of 8 by Lemma 6 and that of the level-3 facilities loses a factor 24 by Lemma
The lemma follows by adding up the multiplicative factors that we lose for level-1, level-2, and level-3 facilities.
Finally, we bound the connection cost.
Theorem Let U be the set of clients and Tuo be the fractional solution for client U. Then, the connection cost of integer solution for client u is at most 8 Evev d(u,, V))..v.
Proof. This follows directly from the fact that the algorithm 4-consistent, via Lemma
Now we are ready to prove Theorem 2.
Proof of Theorem 2. The proof follow by combining Theorem and Theorem 8.
RANDOMIZED ROUNDING ALGORITHM FOR GENERAL OPENING COSTS
In this section, we describe a randomized rounding algorithm for the weighted online facility location problem with the following properties: (a) the rounding algorithm is 7-consistent for some constant ? (this property holds deterministically), and (b) at any time t, the expected facility opening cost of the integral solution is at most Oloo log At) times that of the fractional solution, where A, denotes the aspect ratio of the metrie space at time t, i.e., the ratio of the maximum the minimum (non-zero) distance between any pair of vertices. Formally,
Theorem 9. There exists randomized online algorithm that rounds fractional solution for facility location online and the expected cost of the rounded integral solution O(log log A) - a.), where a denotes the cost of the fractional solution.
In defining the rounding algorithm, it will be convenient assume that the fractional mass yo at any vertex does not change over time. This is without loss of generality by the following standard technique: whenever the fractional algorithm increases the fractional mass at a vertex by some quantity 8, we create second copy of vertex v, namely a new vertex that is at distance 0 from v and the same distance as from all other vertices, and the fractional mass on the new vertex The facility opening cost of the new vertex is the same as that of the original vertex. Clearly, the opening and connection costs of the new fractional solution are identical to the original solution, but this solution has the advantage that the fractional mass rest this paper, we will assume that the fractional solution satisfies this property. We emphasize that this is not an additional assumption the input; rather, it is purely notational transformation that preserves all opening and connection costs and works for any metric space. Moreover, this transformation does not affect the running time of the algorithm beyond constant factors.
vertex is set in only one step. In the
We describe the rounding algorithm next, and then give its analysis Appendix B to establish properties (a) and (b) above.
8

---

Published as a conference paper at ICLR 2026
4.1 RANDOMIZED ROUNDING ALGORITHM
If any vertex has y 1/2, we immediately open facility at that vertex. We call this deterministic rounding step, and the corresponding facilities are called deterministic facilities. Clearly, the total opening cost of deterministic facilities is at most twice their fractional opening cost. In the rest of the description, we focus on how the algorithm opens the rest of the facilities using a randomized algorithm.
The algorithm uses a counter for every vertex e that we call its level and denote ((v). In the following. will say that vertex has been rounded by the randomized algorithm if it has been involved in randomized step of the algorithm. Initially, f(v) = 0. Over time, {(v) tracks the number of times vertex u has been rounded by the algorithm. Since the algorithm rounds vertices randomly, the level counters are random variables. Eventually, we will show that for every vertex the expected value of (vv) at time t is Olog log At). For notational convenience, we also maintain a level counter of value 1 at each deterministic facility. These counters do not change over time.
will be convenient to maintain an order < on all the vertices in the metric space. The precise order is not important, but for consistency, e < o' if appears earlier than v' in the online problem (ties are broken arbitrarily for vertices that appear in the same time-step). We also set up a lexicographic order on all balls B* (u, R) in the metric space, which we also denote <, using the following rules:
(a) if t < t', then Bº (e, R) x B* (v', for any vertices v, v' and radii R, Rt, (b) for any time if (1,,
R < Ri, then B¹ (v, R) x B'(', R(') for any vertices v, v', and (c) for any time i and radius Rt if
v', then (1, R) < (1 R).
At any time t, we call a ball (", R) critical if it satisfies the following properties: (a) the total fractional mass in B¹ R) is at least 1/2. and (b) there is no overlapping critical ball with radius at most 2R that appears earlier in the lexicographic order, i.e., there is no B (v', R') < (' R) with radius R' S 2R such that B" (v', R') n (r,,, R) * 0. Observe that critical balls are defined deterministically since this definition only depends on the fractional solution. We also define the level of a critical ball B == Ba (3,, R) as (B) == min(f: Be V', 2 1/4). Note that although the fact that a ball is critical is deterministic, its level is random since it depends on the values of the level counters which themselves are random variables.
Finally, we define the randomized rounding step. At time t, we consider the critical balls in lexico- graphic order <. For a critical ball B == (v, Rt), if there is an open facility in B already, then we do nothing. Otherwise, we open a facility at a location in B3- := {u E B ((u) S {(B)} with probability proportional to v (In other words, the probability of opening a facility at u E B₃ is vi/E=en, vt)). Correspondingly, we increase by one the level counters {(u) of all locations u E B, This algorithm already sufficient, but for the sake of simpler analysis, we add one more step. For each vertex u E Br, we also open facility at u independently with probability vl. We call the two randomized rounding steps respectively the dependent and independent rounding steps.
Why constant factor remains open in the non-uniform case. We show in Appendix D that the analysis of our randomized algorithm is asymptotically tight. In particular, any improvement over the Ólog log A) bound would require fundamentally new ideas. At a high level, the key structural difference between the uniform and non-uniform settings lies in how facility opening costs can be charged to fractional mass. In the uniform case, the cost of opening a facility at a vertex can be charged to fractional mass in nearby regions of the metric space. This charging argument crucially exploits the uniformity of opening costs. In contrast, in the non-uniform case, the opening cost of facility at vertex cannot, in general, be charged to fractional mass located elsewhere in the metric space.
5 APPLICATION TO LEARNED- FACILITY LOCATION
In this section show how to leverage the presented online rounding algorithms obtain algorithms for the Maaning--augmente facility location.
Our starting point is the online fractional algorithm for in Anand et al. (2022) that gives the following theorem:
facility location presented

---

Published as a conference paper at ICLR 2026
Theorem 10 (Theorem 7.1 from Anand al. (2022) restated). There is algorithm for the fractional online facility location problem that at time produces an online solution with cost (mmin(log(k + dynamic, Tog
log
log opt,) } in the multiple predictions setting with k predictions.
We apply our rounding algorithms presented in Section 3 and Section 4 on the fractional solution constructed Anand al. (2022) to obtain integral algorithms for the carning-augmeen location. In particular, we obtain the following theorems for the uniform (Theorem 11) and non- uniform (Theorem 12) setting. Note that the two theorems obtain consistency bounds of O(log(++1)) log
facility
and Ollog log log(k + 1)) respectively, while ensuring a robustness bound of O Ol log ). (The proofs are deferred to Appendix C. Also recall that, by standard techniques (see Appendix E), the upper bound Ollog log A) may be replaced by Ollog log n).)
Theorem 11. There is an algorithm for the uniform learning-auggennter facility location problem log t_
that time produces online solution with cost O(min(log(( + 1) dynamic, Toglog opt,))
Theorem 12. There an algorithum for the non-uniform tion problem that at time t produces an online solution with cost Omin flog log A -log(: 1) dynamic,, log lug opt, }-
facility loca-
CONCLUSIONS AND FUTURE WORK
We present two new algorithms round online fractional facility location solution and we show how to use them to obtain almost tight guarantees for the questions, it would be interesting to find rounding algorithm for the non-uniform settings that lose only a constant factor in the approximation. It would also be very nice to modify the fractional algorithm in Anand al. (2022) obtain Ommin or show that it is impossible.
facility location algorithms. The algorithms obtains problem and are simple and natural. As follow-up
log dynamic,.
log t log log )pt, "approximmaio
log log
IMPACT STATEMENT
This paper presents work whose goal to advance the field of Machine Learning. The main contribution of the paper is theoretical and is of interest to the domain of designing robust algorithms leveraging machine learning advice.
ACKNOWLEDGMENT
This research project was initiated Dagstuhl Seminar 23061 "Scheduling." " We thank the organizers and Dagstuhl for their support.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice. Advances in neural information processing systems, 34:4661-4673, 2021.
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. A general approach to online network optimization problems. ACM Transactions on Algorithms (TALG), 2(4):640-660, 2006.
Aris Anagmostopoulos, Russell Bent, Eli Upfal, and Pascal Van Hentenryck. A simple and deter- ministic competitive algorithm for online facility location. Information and Computation, 194(2): 175-202, 2004.
Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. In International Conference on Machine Learning, pages 582-598. PMLR, 2022.
Antonios Antoniadis, Themis Goulcakis, Picter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. Advances in Neural Information Processing Systems, 33: 7933 7944, 2020.
Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 65-66.55 SIAM, 2022.
Xingjian Bai and Christian Coester. Sorting with predictions. Advances in Neural Information Processing Systems, 36:26563-26584 2023.
Eric Balkanski, Vasilis Gkatzelis, and Golnoosh Shahkarami. Randomized strategic facility location with predictions. Advances in Neural Information Processing Systems, 37:35639-35664, 2024.
Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning aug- mented algorithms. Advances in Neural Information Processing Systems, 33:20083- 2020.
Marcin Bienkowski, Björn Feldkord, and Pawel Schmidt. A nearly optimal deterministic online algorithm for non-metric facility location. arXiv preprint arXiv:2007.07025, 2020.
Niv Buchbinder, Joseph Naor, and David Waje. Lossless online rounding for online bipartite matching (despite its impossibility). In Proceedings of the 2023 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 2030-2068. SIAM, 2023.
Justin Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pages 3583-3602. PMLR, 2022.
Vincent Cohen-Addad Benjamin Guedj, Varun Kanade, and Guy Rom. Online k-means clustering. In International Conference on Artificial Intelligence and Statistics, pages 1126-1134, PMLR, 2021.
Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, and Nikos Parotsidis. Online and consis- tent correlation clustering. In International Conference Machine Learning, pages 4157-4179. PMLR, 2022.
Dimitris Fotakis. A primal-dual algorithm for online non-uniform facility location. Journal of Discrete Algorithms, 5(1):141-148, 2007.
Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1-57, 2008.
Dimitris Fotakis. Online and incremental algorithms for facility location. ACM SIGACT News, 42(1): 97-131, 2011.
Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, and Nikolas Patris. Learning augmented online facility location. CoRR, 0aas/210..0827,, 2021a. URL https: //arxi/a..ivv org/orgggss... 21.7.00 08277.
11

---

Published as a conference paper at ICLR 2026
Dimitris Fotakis, Loukas Kavouras, and Lydia Zakynthinou. Online facility location in evolving metrics. Algorithms, 14(3):73, 2021b.
Dimitris Fotakis, Evangelia Gergatsouli, Themistoklis Gouleakis, Nikolas Patris, and Thanos Tolias. Improved bounds for online facility location with predictions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 26973-26981, 2025.
Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. Advances in neural information processing systems, 34:2733-22 10:2733-2743,, 2021.
Shaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang. Online fa-
cility location with predictions. In The Tenth International Conference on Learning Rep- resentations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https://openrete
net/ forum?id=DSSE
Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. International Conference on Machine Leariing pages 1975-1984. PMLR, 2017.
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859-1877. SIAM, 2020.
Silvio Lattanzi, Benjamin Moseley, Sergei Vassilvitskii, Yuyan Wang, and Rudy Zhou. Robust online correlation clustering. Advances in Neural Information Processing Systems, 34:4688-463 2021.
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice.
Journal of the ACM (JACM), 68(4):1-25, 2021.
Adam Meyerson. Online facility location. Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 426-431. IEEE, 2001.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65(7)333-35, 2022.
Joseph Naor, Aravind Srinivasan, and David Waje. Online dependent rounding schemes for bipartite matchings, with. In Proceedings of the 2025 Annual ACM-SIAMAAA Symposium on Discrete Algorithms (SODA), pages 3116-3154. SIAM, 2025.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018
Alexander Wei and Fred Zhang. Optimal robustness-consiitenny trade-offs for learning- augmeetee online algorithms. Advances in Neural Information Processing Systems, 33:8042-800 2020.
12


Reviews:
[{"review_id": "97x3WpDMHu", "reviewer": "Reviewer_9sc3", "summary": "This paper studies the Facility Location problem, a fundamental clustering task, in the context of online learning augmented algorithms. The authors identify a key gap in existing research: while strong, nearly tight bounds exist for the fractional version of the problem (where facilities can be partially opened), the integral version (where facilities are either fully open or closed) remains less understood. The paper's main contribution is to bridge this gap by introducing the first online rounding algorithms designed to convert a fractional solution into an integral one efficiently. Two algorithms are presented: first, a deterministic algorithm for the uniform cost case, in which all facilities have a cost of $1$, that achieves a constant $(O(1))$ cost overhead compared to the fractional solution, and second, a randomized algorithm for the non-uniform cost case that incurs an $O(\\log\\log\\Delta)$ loss. By combining these rounding techniques with the known fractional algorithms of Anand et al. (2022), the paper derives the first integral learning-augmented facility-location algorithms with consistency and robustness guarantees that match the previously known ones for the fractional case.", "questions": "- Could you apply similar techniques to directly get an online learning augmented algorithm by treating the input fractional solution as the ML advice?\n- You mention as future work finding a constant-factor rounding for the non-uniform case. What seems to be the main obstacle for that?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "One of the paper’s strengths is its novelty and solid theoretical contribution, as it introduces the first online rounding algorithms specifically for the facility location problem, essentially reducing the integral version of the problem to the fractional one. The paper is also well structured, with proofs that are intuitive and technically involved.", "weaknesses": "The paper title might be a bit misleading as the results are entirely on online rounding algorithms with applications to learning augmented algorithms. The results can be applied to existing learning augmented algorithms, but the novelty is only on the online rounding part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9jnjScFvA5", "reviewer": "Reviewer_CpWi", "summary": "This paper discusses rounding algorithms for the fractional facility location problem under both the cost structures, uniform and non-uniform. That is, when the cost of establishing a new facility is either constant or varies across facility locations. It presents interesting theoretical results that address one of the key open problems of facility location topic. Authors propose online learning algorithms that leverage the solution of the fractional problem to construct solutions for the corresponding integral versions. The algorithms are well-motivated, clearly explained, and supported by sound theoretical reasoning.", "questions": "In addition to the above, I would suggest some clarifications and further discussion on the following points:\n\nIn the absence of computational evaluations, It is not clear to me how the proposed algorithms perform on small-and large-scale instances, especially those with high aspect ratios or complex metric spaces. At least small scale (initial) experimental results evaluating the computational complexity and scalability of the proposed rounding algorithms would be useful. \n\n\nAre there specific optimization techniques that Authors recommend for implementing the algorithms efficiently in practice? \nThe analysis assumes that the fractional mass y^t_v​ remains fixed during the rounding process or can be approximated as such via vertex splitting. Could you comment on real-world scenarios where this assumption may not hold strictly? How would potential violations of this assumption affect the validity or tightness of the approximation guarantees?\n\n\nThe derived bounds naturally depend on the aspect ratio of the metric space, \\Delta_t​. In dynamic or evolving settings where this ratio may vary significantly over time, how sensitive are the theoretical guarantees to such changes? \n\nIn the absence of experimental results, it remains unclear how the proposed methods compare with existing online facility location algorithms, such as those by Meyerson or more recent learning-augmented approaches. A qualitative or theoretical comparison in terms of approximation factors and operational complexity would help position this work within the broader literature.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper presents proposes a novel solution for facility location problem. The requests arrive sequentially and hence this is related to the  clustering (unsupervised learning) problem. The performance measure is approximation ratio. The key idea is to transform the fractional solutions of the online facility location problem into feasible integral solutions. The authors build upon and extend prior approaches that address several key limitations, achieving a better approximation ratio.\n\n\nAuthors consider two main settings: one where the facility setup cost is uniform across all locations, and another where the costs vary by vertex (the non-uniform cost structure). This broader treatment is interesting as the model is more realistic and relevant to practical scenarios.\n\n\nThe paper has strong theoretical depth; the theorems and their proofs developed nicely. While the discussion connects partially to existing literature, the algorithmic descriptions are particularly detailed and well explained. Important notions such as critical balls, randomized rounding, and the role of aspect ratios in determining approximation guarantees are well defined. These explanations enhance the readability of the technical sections; interested readers, who may not be into this area, may also be able to follow.", "weaknesses": "The paper is theoretical in tis nature, focusing on proving approximation bounds and analyzing the properties of rounding algorithms. While the theoretical contributions are strong, the practical relevance particularly in learning-augmented settings could be strengthened through empirical validation. Incorporating simulations or experiments on synthetic or real-world datasets would help demonstrate the applicability of the proposed methods beyond the purely theoretical framework.\n\nNext, several assumptions made in the paper, such as the preservation of fractional mass and the existence of specific geometric or metric properties (e.g., aspect ratio bounds), are not well justified. It is unclear whether these are standard assumptions in prior literature or newly introduced for tractability. If these are common, the authors should explicitly cite supporting works; if they are novel, a more thorough discussion or justification of their necessity and implications is required. As of now, some of these assumptions appear tailored to make the analysis feasible rather than naturally arising from the problem structure. Comments by the Authors are desirable. \n\nThe paper also references the open challenge of achieving an approximation factor of O(log /log log K) in the non-uniform cost case. However, this result is asymptotic, and this limitation is not highlighted in the discussion. It is very desirable if Authors explicitly acknowledge this gap and outline possible directions for bridging this gap.\n\nAs far as the presentation is concerned, several definitions such as critical balls, levels, and probabilistic rounding steps are dense, making it hard to parse. Many readers would like to have easy to explain examples or see illustrations (schematic diagrams); they could greatly enhance the readability for the readers that are less familiar with the literature. \n\nFinally, while the derived bounds involving factors like (log \\Delta) are theoretically interesting, the tightness of these bounds is not well discussed. Clarifying whether these bounds are provably near-optimal or if there is potential for improvement would add depth to the technical discussion. Computational illustrations help here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "t39ED14fZ7", "reviewer": "Reviewer_TNrV", "summary": "This paper studies the online facility location problem under the learning-augmented setting, aiming to bridge the gap between fractional and integral solutions. The authors propose two online rounding algorithms-- a deterministic algorithm for the uniform-cost case achieving a constant approximation ratio and a randomized algorithm for the non-uniform-cost case achieving an $O(\\log \\log \\Delta)$ approximation.\n\nThese algorithms can be combined with existing fractional solutions (Anand et al., 2022) to yield near-optimal integral algorithms for the learning-augmented facility location problem. The work establishes that the main difficulty of the classic online facility location lies in computing high-quality fractional solutions rather than rounding them.", "questions": "1. Could the authors provide empirical or synthetic experiments to demonstrate the actual performance or confirm the tightness of the constants?\n\n2. Is it possible to adapt the rounding framework to directly construct improved fractional algorithms or to other related online optimization problems?\n\n3. How sensitive is the performance to the quality of the fractional input—e.g., if the fractional approximation is only moderately good?\n\n4. The paper argues that the rounding stage is no longer the main source of difficulty in online facility location. Could the authors provide further justification or empirical evidence supporting this claim—for instance, by showing that different fractional baselines yield similar integral performance after rounding?", "limitations": "", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The results provide a conceptual bridge between fractional and integral formulations, advancing the theoretical understanding of online algorithms.\n\n2. The deterministic algorithm achieves constant-factor guarantees, while the randomized version achieves $O(\\log \\log \\Delta)$, improving over previous bounds.\n\n3. The paper tackles an open problem by presenting the first online rounding algorithms for the facility location problem in both uniform and non-uniform cases.\n\n4. The approach extends learning-augmented facility location to integral settings with nearly tight consistency–robustness trade-offs.", "weaknesses": "1. Although the paper successfully extends the known fractional results to integral settings, the achieved approximation and consistency–robustness bounds do not improve upon the theoretical lower bounds established in prior works (Almanza et al., 2021; Anand et al., 2022). In other words, the results are asymptotically tight but not stronger than existing bounds, which somewhat limits the theoretical novelty of the contribution. \n\n2. The technical exposition, while mathematically sound, is dense and could benefit from clearer intuition or illustrative examples of the rounding procedure. \n\n3. The applicability of the rounding framework to other online covering problems (e.g., online set cover, k-median, or caching) is not discussed, which limits the broader impact of the work. \n\n4. Although the theoretical results close an existing gap between fractional and integral formulations, the technical novelty of the algorithms themselves seems incremental. Many arguments (e.g., in Lemma 1 and Theorem 2) follow standard geometric consistency proofs, and the randomized rounding procedure closely resembles existing metric-dependent rounding techniques. As a result, the contribution may feel more like a careful synthesis of known tools than a fundamentally new technical breakthrough. \n\n5. The paper is entirely theoretical. There is no experimental validation or numerical evidence illustrating the practical behavior of the algorithms or how large the hidden constants are in real settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VRjofx6MEg", "reviewer": "Reviewer_jk99", "summary": "The paper presents the first online rounding algorithms that convert fractional online facility-location solutions into integral ones while preserving competitive theoretical guarantees. The main results include: (1) a deterministic constant-factor rounding algorithm for uniform opening costs, and (2) a randomized rounding algorithm for non-uniform costs with $O(\\log\\log\\Delta)$ expected loss, where $\\Delta$ is the aspect ratio of the given instance. These rounding schemes are then plugged into prior fractional, learning-augmented (multiple-predictions) algorithms to yield the first integral solutions with $O(\\log(k+1))$ (uniform) and $O(\\log\\log\\Delta\\log(k+1))$ (non-uniform) consistency, together with $O(\\log t/\\log\\log t)$ robustness via a combiner. A lower bound shows the $O(\\log\\log \\Delta)$ dependence is asymptotically tight for the randomized scheme, supporting the claim that the main hardness is obtaining a strong fractional solution rather than rounding it.", "questions": "1. It is unclear for me that why the online setting is the right lens (irrevocable decisions under partial information), and why rounding—rather than runtime—is the key bottleneck.\n\n2. Could you instantiate the model with a simple scenario (e.g., two competing predictors) and show how your rounding plus the combiner behaves under accurate vs. adversarial advice?\n\n3.  Can the randomized rounding guarantee be made $O(\\log\\log n)$ in the main text (not only via Appendix E’s reduction), or do structural barriers preclude this?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The uniform-cost algorithm is 4-consistent with a constant-factor competitive cost. For non-uniform costs, the algorithm is 5-consistent and can control the expected facility cost via a vertex-level scheme, achieving $O(\\log\\log \\Delta )$. The resulting level/critical-ball construction is clear and metric-aware. Combined with the fractional learning-augmented algorithm of Anand et al. (2022), the rounding process yields the first integral multiple-prediction results with nearly-tight consistency and robustness guarantees. A matching $\\Omega(\\log\\log \\Delta)$ lower bound shows this dependence is unavoidable for randomized rounding, supporting the claim that the main hardness lies in finding a strong fractional solution, not in rounding. Finally, the appendix gives a reduction that trades $\\log\\log \\Delta$ for $\\log\\log n$, which is useful when $\\Delta$ is large with moderate data size $n$.", "weaknesses": "The main weakness can be summarized as follows.\n\n1. For non-uniform costs, the guarantees scale with the metric aspect ratio $\\Delta$ (or, via reduction, with $n$), which can be large in practice. \n\n2. The robustness improvement chooses the cheaper of two online solutions by opening all its facilities, while facilities opened by the other solution remain. This preserves guarantees but can monotonically increase the number of open facilities over time; the paper does not analyze recourse or stability beyond competitive cost.\n\n3. It is suggested that the paper should clarify the novelty, where the proposed  is the first online rounding algorithms for metric facility location, not the first results on online facility location overall. \n\n4. Because the three-level ball scheme is central, giving an explicit example before Conditions A/B/C would make the presentation clearer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)