Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
Authors: Nate Veldt
Thomas Stanley
Benjamin W Priest
Trevor Steil
Keita Iwabuchi
T.S. Jayram
Grace J Li
Geoffrey Sanders
Venue: ICLR 2026 Poster (2026)
Keywords: Minimum spanning tree
metric spaces
learning-augmented algorithms
algorithms with predictions
approximation algorithms
dynamic programming
k-center
Primary area: learning on graphs and other geometries & topologies
TL;DR: We present a generalized learning-augmented algorithm and improved approximation guarantees for finding a metric minimum spanning tree

Abstract: We present improved learning-augmented algorithms for finding an approximate minimum spanning tree (MST) for points in an arbitrary metric space. Our work follows a recent framework called metric forest completion (MFC), where the learned input is a forest that must be given additional edges to form a full spanning tree. Veldt et al. (2025) showed that optimally completing the forest takes $\Omega(n^2)$ time, but designed a 2.62-approximation for MFC with subquadratic complexity. The same method is a $(2\gamma + 1)$-approximation for the original MST problem, where $\gamma \geq 1$ is a quality parameter for the initial forest. 
We introduce a generalized method that interpolates between this prior algorithm and an optimal $\Omega(n^2)$-time MFC algorithm. Our approach considers only edges incident to a growing number of strategically chosen "representative" points. One corollary of our analysis is to improve the approximation factor of the previous algorithm from 2.62 for MFC and $(2\gamma+1)$ for metric MST to 2 and $2\gamma$ respectively. We prove this is tight for worst-case instances, but we still obtain better instance-specific approximations using our generalized method. We complement our theoretical results with a thorough experimental evaluation.

Published as a conference paper at ICLR 2026
BETTER LEARNING-AUGMENTII SPANNING TREE ALGORITHMS VIA METRIC FOREST COMPLETION
Nate Veldt', Thomas Stanley', Benjamin W. Priest Trevor Steil Keita Iwabuchi,, T.S. Jayram'. Grace J. Li. Geoffrey Sanders² TTxas A&M University. LLawrence Livermore National Laboratory fnveldt, thomas. (taaaeyyetaallt (priest2, steill, heepii,,,wwubuhhtr iwabuchi1, 1,
edu
haaaaii1,hhhhhhhhhae thathacharl, 1i85, sanders29) gov
ABSTRACT
We present improved carmine-augmented algorithms for finding approximate minimum spanning tree (MST) for points in an arbitrary metric space. Our work follows recent framework called metric forest completion (MFC), where the learned input is a forest that must be given additional edges to form full span- ning tree. Veldt et al. (2025) showed that optimally completing the forest takes ((n2)) time, but designed 2.62- a2-aappoxintttion for MFC with subquadratic com- plexity. The same method is (2y + 1)-approximation for the original MST prob- lem, where 7 2 1 is a quality parameter for the initial forest. We introduce a generalized method that interpolates between this prior algorithm and an optimal 12(n))-tmme MFC algorithm. Our approach considers only edges incident to a growing number of strategically chosen "representative" points. One corollary of our analysis is to improve the approximation factor of the previous algorithm from 2.62 for MFC and (2 + 1) for metric MST to 2 and 2 respectively. We prove this is tight for worst-case instances, but we still obtain better instance-specific approximations using our generalized method. We complement our theoretical results with thorough experimental evaluation.
INTRODUCTION
Finding a minimum spanning tree (MST) of a graph is fundamental computational primitive with applications to hierarchical clustering (Gower & Ross 1969 Gagolewski et al.) 2025 La Grassa
et al. 2022). network design (Loberman & Weinberger 1957). feature selection (Labbé et al. 2023), and even comparing brain networks (Stam et 2014p. The metric MST problem special case where the input is set of points, and edge weights are defined by distances between points, A conceptually simple algorithm for this case to compute all (n²) distances explicitly and then apply a classical greedy algorithm. For Euclidean metrics, there exist more sophisticated algorithms that can find an optimal or at least approximate minimum spanning tree in o(n²) time (Agarwal et al,, 1990 Shamos & Hoey 1975, Vaidya 1988 Arya & Mount. 2016). For general metric spaces, however, one must know 2( edges to compute even an approximate solution [Indyk] 1999).
This fact constitutes fundamental challenge for designing algorithms that scale massive modern datasets, apply to general distance functions, and come with provable guarantees.
Motivated by the above challenge, our previous work (Veldt et al., 2025) recently addressed the metric MST problem from the perspective of Vassilvitskii 2022). The augmented model assumes access to prediction for some prob- lem, often produced by a machine learning heuristic, that comes with no theoretical guarantees but may still be useful practice. The goal is to design an algorithm that can obtain better than worst- case guarantees using the prediction. The performance of the algorithm is typically captured by some parameter measuring the error of the prediction. The prediction, performance measure, and error parameter vary depending the context. Some prior work focuses on netter-than-worst-cco runtimes or query complexities, including for binary search (Mitzenmacher & Vassilvitskii 2022] Dinitz et al. 2024), maximum flow (Polak & Zub 2024 Davies et al. 2024; 2023). ), and incremental approximate shortest paths (McCauley et al. 2025). Other works focus on improving competi-
algorithms (Mitzenmacher &
tive ratios for online algorithms, including for ski rental (Mitzenmacher & Vassilvitskii 2022 Shin

---

Published as a conference paper at ICLR 2026
2023) scheduling (Benomar & Perchet 2024), and online knapsack problems (Lechowicz et al.
et al. 2024). In other settings, the goal is to improve approximation ratios for hard combinatorial
problems, e.g., clustering problems (Braverman al. 2025 Ergun et al. [2022] Nguyen al. 2023
Huang et al. 2025) or maximum independent set (Braverman et al. 2024).
For the metric MST problem,
recent work (Veldt et al. 2025) introduced a
setting where the n points are partitioned into components and each component is associated with a tree on its points. This input is called the initial forest, and can be viewed as a prediction for the forest that would be obtained by running several iterations of a classical algorithm such as Kruskal's. s.. Metric forest completion (MFC) is then the task of finding a meniimmm-wighht spanning tree that contains the initial forest as a subgraph. The quality of an initial forest is captured by a parameter
y 2 1, where ? = if the initial forest is contained in some optimal MST. We previously proved that optimally solving MFC takes (2(n²) time, but gave a 2.62-approximmaiion algorithm whose runtime depends on the number of components t, and has subquadratic complexity if o(n) (Veldt a algorithm for metric MST with an approximation factor of (2 + 1). The algorithm identifies a single representative node for each component in the initial forest, and only considers edges incident to one two representatives. Implementations of the algorithm produced nearly optimal spanning trees while being orders of magnitude faster than the naive R(n=) algorithm for metric MST. This is true even after factoring in the time to compute an initial forest. The in-practice approximation ratios also far exceeded the theoretical bounds of (2y+ + 1) (for the original MST problem) and 2.62 (for the MFC step) on all instances.
2025). The same method is a learning-augmenti
generalized algorithm and tighter bounds. While our prior work already demonstrates the theoretical and practical benefits of the MFC framework, several open questions remain. Is the large gap between theoretical bounds and in-practice approximation ratios due mainly to the specific datasets considered? Are there pathological examples where the previous approxi- mation guarantees are tight? In the other direction, can we tighten the analysis to improve the worst-case approximation guarantees? Also, can we prove better instance-specific approximations?
Our contributions:
We introduce and analyze generalized approximation algorithm for MFC that provides a way to ad- dress all of these questions. This algorithm starts with a budget for the number of points in the dataset that can be labeled as representatives. It then finds the best way to complete the initial forest by only adding edges incident to one or two representatives. Choosing one representative per component corresponds to applying our prior approximation algorithm (Veldt et al. 2025). Letting all points be representatives leads to an optimal (but (((n)-ttmm)) algorithm. Our new approach interpolates between these extremes, and for reasonable-sized budgets provides way to significantly improve on the prior algorithm with only minor increase in runtime. We derive new instance-specifer bounds on the approximation factor for this generalized approach, given in terms of casy-to-compute cost function associated with a set of representatives. As an important corollary of our theoretical results, we prove that when there is only one arbitrary representative per component, the algorithm is a 2-approximation for MFC and a 27-approximation for metric MST. This immediately improves on the approximation factors of 2.62 and (2y + 1). Furthermore, our analysis both simpler and more general. We also prove by construction that these guarantees are tight in the worst case.
As technical contribution of independent interest, we show that choosing the best set of represen- tatives for our algorithm amounts to new generalization of the k-center clustering problem. For this generalization, we have multiple instances of points to cluster, but the budget & on the number of cluster centers is shared across instances. We design 2-approximation for this shared- multi-instance k-center problem by combining a classical algorithm for k-center (Gonzalez 1985) with dynamic programming approach for allocating the shared budget across different instances.
As a final contribution, we test an implementation of our new algorithm on a range of real-world datasets with varying distance metrics. We find that increasing the number of representatives even slightly leads to significant improvements in spanning tree quality with only a small increase in runtime, and that our dynamic programming approach performs especially well. Furthermore, our instance-specific approximation guarantees are easy to compute and serve as a very good proxy for the true approximation factor, which is impractical to compute exactly.
2

---

Published as a conference paper at ICLR 2026
2 PRELIMINARIES AND RELATED WORK
For m E N, let [m]] = m. For an undirected graph G (V, E) and edge weight function w: E + R. minimum spanning tree (MST) for G with respect to is tree T = (V, Er) where
ET C E' and the total weight of edges w(Er) = EeeEr w(e) is minimized. Optimal greedy
algorithms for this problem have been known for nearly a century (Borûvka 1926; Kruskal [956]
Prim] [1957). For example, Kruskal's algorithm starts with all nodes in singleton components, and at each step adds a minimum weight edge that connects two disjoint components. Borúvka's 's algorithm is similar, but adds the minimum weight edge adjacent to each component every round.
The metric MST problem. Let (Z, be a finite metric space defined by a set of points X = fr1, 20,,22,..-,. J and distance function d: X' x X - R+ This input implicitly defines complete graph Gx = (X, Ex) with an edge function wx that is equivalent to the distance function d. We let (u, v) denote the edge in Gx defined by points (un,Ty) with weight wx (u, v) d(z,,; For two sets X, Y C X, define d(X, Y)= = min EXEYY d(z,, y)- We extend wx to a weight function on an edge set F S Ex by defining wx (F) = E L(a.))EF wx(u, v). The metric MST problem the task of finding a minimum spanning tree of Gx with respect to wxx
A conceptually simple approach for metric MST is to query all O(n²) distances and apply a classical algorithm to the resulting complete graph. Another approach that still takes 22n2)) time for general metric spaces but avoids querying all distances is an implicit implementation of classical method, which only queries distances as needed (Agarwal et al. 1990, Callahan & Kosaraju 1993). In more detail, an implicit implementation of Kruskal's 's or Borúvka's is algorithm starts with all points as singleton components. At every step of the algorithm, for each pair of components A and B, the algorithm finds pair of points (a. b) E A x B with minimum distance. This is known as the bichromatic closest pair problem (BCP) for A and B. An implicit implementation of Kruskal's algorithm would then add the minimum weight edge from among all the BCP problems. An implicit implementation of Borůvka's s algorithm would add one edge for each component.
The initial forest for learning-augmentee MST. When applying Kruskal's 's or Borúvka's 's algorithm implicitly to X, terminating the algorithm early would produce a forest of disconnected compo- nents (see Figure Tay. Inspired by this observation, we recently introduced a learning-augmente framework for metric MST where the input can be viewed as a heuristic prediction for the forest that would be produced by terminating a classical algorithm early (Veldt et al. 2025). Formally, an initial forest G. = (X, F.) for (X' d) is defined by partitioning P (P1, P2... ..... P.} of X' and partition spanning tree T, (P;, Er,) for each E [t] such that E, = Uf_ ET.- See Figure Ic Let P(x)) denote the partition x E X' belongs to in P. We say T; is the ith component of G..
Terminating an exact algorithm early to find an initial forest is prohibitively expensive if one wants to avoid quadratic complexity. One alternative is to run fast clustering heuristic (e.g., the simple 2-approximation for k-center Gonzalez (1985) to partition X, and then recursively find an approx- imate or exact MST for each partition. Another approach is to compute an approximate k-nearest neighbors graph for Gx and then find a spanning forest of it. These and other similar strategies have already been used in prior work to develop fast heuristics (without approximation guarantees) for Euclidean MSTs (Almansoori et al. 2024 Chen 2013) Zhong et al., 2013 Jothi et al., 2018). One contribution of our prior work (Veldt al. 2025) was formalize the notion of an initial forest and introduce a way to measure its quality. To define this measure, let Tx denote the set of MSTs of Gx. For a tree T Tx. let T(P) {u, v) E T: P(u) P(w)} be the set of edges from T whose endpoints are from the same partition of P. The y-overlap of P is defined to be
wx (Fx)
7PP) =
maXTETx wx (T()))
In other words, 7(P) captures the weight of edges that the initial forest has in P, divided by the weight of edges that an optimal MST places inside components. Lower values of y are better, as they indicate that the initial forest overlaps well with some optimal solution. One can use the minimizing property of MSTs to show that (P)) 2 1, with equality exactly when G, is contained inside some optimal MST. When P is clear from context, we will simply write 7 = 7(P).
3

---

Published as a conference paper at ICLR 2026
(a) Kruskal stopped early
(b) Completed MST
(c) Initial forest (P; (T:))
(d) MFC solution
Figure 1: (a) The forest obtained by terminating Kruskal's ' algorithm early for set of 100 points. (b) Running Kruskal's algorithm to the end leads to full MST. (c) The initial forest can be viewed a heuristic prediction for the forest in (a). For this example, (PP) se 1.06. (d) Solving metric forest completion problem produces a full spanning tree that approximates the true MST.
Metric forest completion. Given an initial forest, Metric Forest Completion (MFC) is the task of finding a minimum weight spanning tree that contains Eg as a subgraph. Formally:
minimize subject to
wx (ET) T = ET, is a spanning tree for Gxx E, S ET.
(1)
This is equivalent to finding minimum weight set of edges M C Ex such that M completes E,,
meaning that M U E, spans X. Solving MFC for an initial forest where (P) = (e.g.. obtained by terminating exact algorithm early) produces an optimal MST (Figure lb Applying it initial
forest with (P) > 1 (Figure Ic] produces an approximately optimal spanning tree (Figure ld].
MFC can be viewed an MST problem defined over complete coarsened graph Gp (Vp, Ep) where Vp {u1, .. v1
is the node set and Ep (Kr) is all pairs of nodes. Node corre- sponds to partition P. for each i E [t), and the weight between e and n is defined as the solution to the BCP problem between P. and P, Formally, the weight function w" Ep - IR+ is given by
w" (vi, U1y d(P,, Py).
Finding an MST of Gp with respect to w", and then mapping the edges in Gp back to the points in X' that define the weight function w", solves the MFC problem. The challenge is that exactly computing w" can take M(n²)) distance queries, in particular when the component sizes are balanced.
Existing MFC approximation. Our previous MFC-Approx algorithm approximates MFC by consid- ering only a subset of edges (Veldt et al. 2025). This algorithm selects one arbitrary representative point r; P. for each E [T] and completes the initial forest by adding only edges that are in- cident to one or two representatives. Conceptually this amounts to forming a new weight function w: Vp + IR+ such that w' S ă. and then finding an MST in Gp with respect to t. Previously we showed that this can be accomplished in O(nl2x) time (when G. is given), where Qx is the time to query one distance in X. We proved that this algorithm returns a spanning tree that approximates the MFC problem to within a factor (3 + /5)/2 < 2.62. Furthermore, it a augmentd al- gorithm for the original metric MST problem with dereneeerr approximation guarantee of (2> +1 /47 + 1)/2 (2 + 1) (Veldt et al. 2025).
MULTT-REPRESENTTTIIV MFC ALGORITHM
We present a generalization of MFC-Approx that selects a set of representatives for each component, rather than only one. For each i E [4]. let R2 C P. be nonempty subset of representatives for the ith component in P. Let -f R, and define FR = ((r,)): r E R, x E X). The new algorithm finds a minimum weight set of edges M S Fn to complete the initial forest. To do so, it finds an MST of the coarsened graph Gp with respect to a weight function w: Ep - R given by
((,,, v,) = min [d(P,, R,), Rc),
(3)
For each pair (va, vy), the algorithm keeps track of the points x, y E X such that ((;,, uy) d(x, v). in order to map an MST in Gp back to the edge set M C En- We denote this algorithm by MultiRepMFC(R)) R) MultiRepMFC when R is clear from context. By design, MultiRepMFC is
4

---

Published as a conference paper at ICLR 2026
simple way to interpolate between the existing MFC-Approx algorithm and exact algorithm (when R = X). Our key technical contributions are to provide an approximation analysis for this algorithm
(Section 3.1 and present approximately optimal strategy for selecting R (Section 3.2
3.1 APPROXIMATION ANALYSIS FOR FIXED R.
To quantify the quality of spanning trees returned by MultiRepMFC( (R), define the cost of P; to be the maximum distance between any point in P. and its nearest representative:
cost(P, R.) = max min d(x, r). zEP; PER;
(4)
We extend this to a cost function on P by defining cost(P, R) = Ei= cost( Ps. R.). When R clear from context, we write cost(P:) cost (P,, R2) and cost(P) cost(P, P, R).. The following theorem uses this cost to define an instance- multiplicative approximation bound.
Theorem 1. MRlt))epMFO(R) an a-approximation for MFC and an (arr)-approimmation for metric MST where is the overlap parameter for the initial forest and a = 1 cost R)/wx EE.)
Proof. Let TV denote an MST for the coarsened graph Gp with respect w* as defined Eq. 2 This Tp can be mapped to an edge set M C X that optimally solves MFC. Let T be the spanning tree for Gx obtained by combining M with the initial forest edges E,. Thus,
wx(
(xx(M*) + wxx(F = w² (TP) + mcx(F..)
(5)
Let T. be the MST in Gp with respect to v that MultiRepMFC finds, and M be the edge set in X corresponds to. Then the spanning tree ÿ returned by MultiRepMFC has weight
"x( = wx (M + (x((E)) w(fp) + wx (Et).
(6)
Since T% is tree, we can assign each edge in Tp one of its endpoints in such way that one node Gp assigned no edge, and every other node in Gp assigned to exactly one edge of Tp. This can be accomplished by selecting a node of degree from T.p, assigning s's only incident edge to v, and then removing v and its incident edge before recursing. This continues until there only one node of G with no adjacent edges. We write U;) Th indicate an edge in this tree between v and by that is assigned to node v; Since each node is assigned at most one edge, we have that
Σ (ET
cost(P.) S Σ cost( cost(P).
For an arbitrary edge (t,, Tp, let (Ia, No) P. P3 be points in X defining the optimal edge weight w" (vi, 02) d(Ea; 2n). Let E Rg be the closest representative in P; to point Ta meaning
d(Ia, 2) = min d(za, r) S max min d(x, r) = co.)(P.).
rE
P, EER;
By definition, w(v,, vj) is most the distance between z and any point in Pj. which implies that (0;,; v3) S d(2, 2b). Therefore
( 03)) S d(2,,t) S d(r,, ms) + d((aa2) S w" (v:, + cost P.).
(8)
Combining the bounds in 7 and (8) gives
u (T²))
Σ w(0,, 13) S Σ
(w, U,) + cost(P.)) s w wT(T)) cost(P).
(TT
Putting these observations together proves the approximation for MFC:
(x = :((Tp) + ux (E²)
(Eq.
< (TT)) + wx ( (Ez)
(Tp is optimal for ii
I w (TT) + cost(P) + + (xx(E))
(Eq.
(x*) + cost(P)
(Eq.
s <1+ cost(P)
wx (xxx(""
wx(Ee)
5

---

Published as a conference paper at ICLR 2026
(3)
404
0
0
0
0
0
0
0
0
0
0
Figure 2: The MFC instance from Theorem when e 3 and p = 5. Initial forest edges are black solid lines. Points with black centers are representatives. Two points have distance & if they are in the same gray enclosing region, otherwise they have distance 1. Adding red dashed edges produces the optimal spanning tree. MultiRepMFC only adds edges incident to representatives, and therefore completes the forest with 1 edges of weight (e.g., dotted blue edges).
where in the last step we have used the fact that (x, S Wx(T"). To turn this bound into an aap)--appoinnnaion for the original MST problem, suffices to prove wx (x"T") S (Tx(Tx)) where Tx is an MST of Gx that leads to the smallest overlap parameter y for the initial forest. Let Ix denote the of edges of Tx that are inside components P, meaning that
Wx E.) = -x
(10)
Furthermore, let Bx = Tx Ix be the set of edges in Tx that cross between components of P. Observe that Bx must correspond would not provide connected path between all pairs of components and hence would not span Gx. The fact that Tp is a minimum weight spanner for Gp guarantees that w" (Tş) S (xx(xx). Combined with (T)) this gives the desired inequality:
spanning subgraph of the coarsened graph Gp. If not, Tx
w.x x (T*) wxx (E.) w" (Tş) S Tru (Ix) + ux (Bx) S (xx((xx)
As corollary, we improve on the previous analysis that proved MFC-Approx is 2. 2.62-approximmttion for MFC and (2y + approxxiittoo for metric MST.
Corollary MFC-Approx is a 2-approximation for MFC, and (24) (22))aaprxximation for MST where y is the overlap parameter for the initial forest.
Proof. MFC-Approx is equivalent to MultiRepMFC when RG is a single arbitrary point from P; for each i (1,2....,4] We know cost(P;) (P,) S wx((T), since cost Pt) equals the distance between two specific points in P.. and there is path between these two points in T. Summing across all components gives cost(P) S wx (Ee). This in turn implies that a < proving the bound.
In addition to providing better approximation factors, our analysis is shorter and simpler than the prior analysis for MFC-Approx. See Appendix for a more detailed comparison.
The following result shows that our approximation guarantees are tight in the worst-case. In particu- lar, for a fixed number of representatives per component, the approximation factor in this theorem converges to 2 = 2 as p + oo and = 0.
Theorem 3. Let and be arbitrary positive integers, and e E 10,1) be arbitrary. There exists an initial forest with (PP) 1 and choice of representatives per component for which MultiRepMFC returns a tree that is a factor
(2 Ls -)ppppp-
(1 + Et)p
larger than the tree returned by optimally solving MFC (equivalent here to the metric MST problem).

---

Published as a conference paper at ICLR 2026
Proof. We will create initial forest with components, each with E+1 points, of which l are rep- resentatives. All points will be represented by (p+ pdimenninai vectors, where p' = max p)- Let x! denote the jth point in the ith component, where [p] and j {0, 1,...,.) (). More precisely, for i E [p + p'I. I, let e, be the (p + p') vector that is all zeros except for a in the ith entry. For [p] define (0)
epts and x
( e; e Eptj for E [c].
Let R = { (x) E [t.j E [4] denote the set of representatives. Let 5 = { [
(0) i E [1] be the
remaining points, which refer small points since they have norm We consider the vector space X' = R U S where distance is defined by the too norm. This means that
if i = and b > 0 and j > 0
(xx))x=11)))) |10 x 11
if b- otherwise.
In other words, the distance between two representatives the same component e, the distance between two points in S is and the distance between every other pair of points is 1. See Figure
To define the edges E, in the initial forest, for each [4] add an edge from 2,(0) to x; (++1) for 1. The first edge has weight I, and the next e - edges have weight E. Thus, the weight of the initial forest is:
j = 1,....., f-
w Ex) = p.p.....-
Since < 1. the optimal solution to MFC is to add spanning tree on small points. This costs 8 (p - 1), so if T represents an optimal tree for the MFC problem,
wx (Tx = p.p... (
e(p 1) (1 =t)p c.
(11)
One can check that this tree is also optimal for the MST problem, so y(P) =.
MultiRepMFC only adds edges that are incident one or more representatives, this algorithm adds p edges of weight Thus, if f is the tree returned by the algorithm, we have
-x( -
1) + (p - = (2 el c)p
Taking the ratio wxx xxx22) (T))/x((T') yields the stated approximation factor.
Theorem B holld for a pathological construction and arbitrarily chosen representatives. By choosing representatives strategically, the upproximation guarantee in Theorem I can far better in practice.
3.2 THE BEST REPRESENTATIVES PROBLEM
We now focus on finding a R that optimizes the approximation ratio in Theorem I Let be nonnegative budget, denoting the number of representatives R is allowed to contain beyond having one representative per component. The Best Representatives problem (BESTREPS) is defined as:
minimize subject
cost(P, R) =t =1 maX min d(z, R&
Vi 4
(12)
Σl R 1) b. b.
Ift this is equivalent to k-center with l: b + 1. Thus, BESTREPS is generalization of k-center where there are multiple instances of points to cluster and the budget for cluster centers is shared across instances. Since the problem is NP-hard even for t 1, it impractical to solve optimally. However, we obtain a fast 2-approximation by combining an approximation algorithm for standard k-center (the = case) with a dynamic programming strategy for allocating budgets
Greedy k:cenneer for approximating allocation benefit. For E [t], we define
c
min R2: R2
cost( P., Ra) for j E [b+11 +11.
An L.M was used to search for related work for this multi-instance k-center generalization, and also generated ideas for developing the 2-approximation algorithm for it. See Appendix B for details.

---

Published as a conference paper at ICLR 2026
This captures the benefit for allocating i representatives to cluster P. Computing c (j) is equivalent to solving an NP-hard h-center problem on the set P. with = We efficiently approximate this function for all S b + 1 by running the greedy 2-approximation of Gonzalez (1985) for k-center with l: = b ++1 1. This method starts by choosing an arbitrary first cluster center. At At j S k, it chooses the jth cluster center to be the point that is farthest away from the first j - cluster centers.
Let R be the the first j cluster centers found by this procedure, and define
a = cost P. Ri,j) for j E [b 1].
By the algorithm's s Srrttt'''s2-appooon 2-approximation guarantee, we know &(j) S 2c, for i E [t] and j E [6 11. DP for allocating representatives. We allocate representatives to components by solving
Σ (a(b:+1) subject to Σ b, = b and b; 2 O E
minimize
(13)
where 6; 2 0 represents the number of extra representatives assigned to P. This is a variant of the knapsack problem where the objective function is nonlinear, all items have weight 1, and we allow repeat items (b: 2 1). If the è; functions are already computed, this can be solved optimally in Ottb²) time via dynamic programming (DP). The DP approach for problems in this form is standard. We provide full details in Appendix [ for completeness, as well as proof for the following result.
Theorem 4. Let {b. i E [t]] be the optimal solution to Problem [3 For E [t], define R& to be the first b; + 1 cluster centers chosen by running the greedy 2-approximation for k-center on P..
Then (R:: i E [4] is 2-approximate solution for BESTREPS.
3.3 ALGORITIM VARIANTS AND RUNTIME ANALYSIS
We now summarize several different approximation algorithms for MFC (and their runtimes) that obtained by combining MultiRepMFC with different strategies for finding R. See Appendix C for more details. We assume / = (nn²) ) for some ò E [0, 1). Let DP-MultiRepMFC denote the algo- rithm that runs MultiRepMFC after finding set of representatives using the dynamic programming strategy from Theorem 4 It has runtime of On1 (b+ t) + tb²). approach that greedily allocates representatives components iteratively in a way that leads to the best improvement to the objective in Problem B3 at each step. It has a runtime of x(1 (b + t)). Fixed MMMtiiieeRPP is a simple baseline that chooses é 2 representatives per component by running the greedy 2-approximation for k-center on each component with & = f. It has runtime of ( (b)) but only applies to budgets 6 that are multiples of All three of these algorithms are 2-approximations for MFC (and bearning-augmentt
is a faster
27-approximations for metric MST) by Theo- rem]] I The asymptotic bottleneck for all three runtimes is computing ω. Rreedd-MultiRepMFF are faster than OP-MultiRepMFC. but OP-MuliReeMMFG is the only method that satisfics an approximation guarantee for the BESTREPS step. The runtimes above assume that the initial forest is already given. If one factors in the time it takes to compute the initial forest, choosing representatives constitutes an even smaller portion of the runtime.
and
4 EXPERIMENTS
Prior work has already shown that the MFC framework (which includes both computing an initial forest and running MFC-Approx) is fast and finds nearly optimal spanning trees for a wide range of dataset types and metrics. Since our work focuses on improved algorithms for the MFC step, our ex- periments also focus on this step, rather than again comparing the entire MFC framework against an exact (((n2)-time algorithm for metric MST. We specifically address the following questions relating to MultiRepMFF, our approximation bound a, and strategies for choosing representatives.
Question 1: How does MultiRepMFG compare (in terms of runtime and spanning tree cost) against the MFC-Approo algorithm (b 0) and the 2(n2) algorithm for the MFC step (b = n??
Question 2: What is the runtime vs. quality tradeoff between using different strategies for approxi- mating the BESTREPS step in practice (Dynamic, Greedy, (f))?
Question 3: How does our instance-speciffe approximation bound (a in Theorem T compare to the worst-case 2-approximation and the actual approximation achieved in practice?
8

---

Published as a conference paper at ICLR 2026
== =ost -1
30
10:40
10"a
10
10:30
10
10
10
10
10
15.
10-10
1000
2500
1000
2000
3000
100
200
300
400
500
100
120
140
10-
10020
Ea =0
10-25
10-9-
10
10-h-
10-25
10
10 A1
10:21
10
10"11
1000
2500
1000
2000
3000
100
200
300
400
500
120
140
Raot
10-13_
10
10 100
10
10-
10.90
20
10.25_
10-31_
10
10-
10 42
1000
2500
1000
2000 Runtime (s)
3000
100 200 300 400 sbo untiim (s)
100
120
140
Runtime (s)
Runtime (s)
(a) Cooking (Jaccard)
(b) GrGenes (Hamming)
(c) Fashion (Euclidean)
(d) Names (Levenshtein)
Dynamic
Fixed
Greedy
Figure 3: We display the performance of each variant of MultiRepMFC as runtime increases. Each point corresponds to running one method with a fixed budget 6. The top row shows the value of e such that method obtains a (1 + -ppproxximttoo in practice. The second row shows the value Ea such that we can guarantee a (1 + apprrxxiimai using Theorem I Computing fast. Computing s is impractical as it requires optimally solving MFC. The last row shows the gap between and the true approximation as runtime increases. We see that all variants of MultiRepMFC provide a useful interpolation between the existing MFC-Approx algorithm (b = 0 vertical dashed line) and optimal MFC algorithm (right vertical dashed line). All plots also show that dynamic programming produces better true approximations (top row), much better approximation bounds (middle row), and is faster shrinking the gap between the bound and true approximation (last row). For Cooking, 16 random orderings of the entire dataset (n = 39, 774) were used, for all others take 16 uniform random samples of size 30, 000. Average results then displayed.
is
Implementation details and experimental setup. Our algorithm implementations are in C++ and directly build on the open-source code made available for MFC-Approx in our prior work (Veldt ct al. 2025). We also apply similar experimental setup. We compute initial forests by partitioning X using a k-center algorithm and then finding optimal MSTs for partitions. We choose t = /n partitions since this approximately minimizes the asymptotic runtime for computing spanning tree (when including the time to form the initial forest); see Appendix Co more details. We consider datasets also used previously (Veldt al. 2025), chosen since each corresponds to different dataset type and distance metric. These are: Cooking (set data; Jaccard distance), GreenGenes (fixed-eenghh sequences; Hamming distance), FashionMNIST 784-dimensional points, Euclidean distance), and Names-US (strings; Levenshtein edit distance). See Appendix D for more details on datasets.
To address our three questions, we run DP-MultiRepMFC. Greedyy-MultRepMFC. and Fixed(()- MultiRepMFC for range of budgets b. For our comparisons, we also run MFC-OPT: an optimal algorithm for MFC that finds an MST of the coarsened graph with respect to the optimal weight function w*. Each run of each algorithm produces spanning tree that completes the initial forest. To measure spanning tree quality, we compute the Cost Ratio for MFC: the weight of the spanning tree produced by the algorithm divided by the weight of the tree produced by MFC-OPT, We also compute a from Theorem [ which is an upper bound for Cost Ratio. This bound a differs for each algorithm and choice of b, since it depends on how well the BESTREPS step is solved.
The first row of Figure 3 displays Cost Ratio - versus runtime for each algorithm. Note that Cost Ratio - 1, this means the algorithm achieved (1 + apappooximation. For the r-axis, the runtime includes the time for approximating BESTREPS plus the time for MultiRepMFC. The second row of plots displays e.,
in the y-axis. This shows us the value of e. for which we can

---

Published as a conference paper at ICLR 2026
guarantee an algorithm has achieved at least (1 + apprrxxmmaann by Theorem | The third row of plots displays a Cost Ratio, which is the gap between our bound on the approximation factor and the true approximation factor. In Appendix D] we show results for all these metrics as the budget varies. However, this does not provide as direct of a comparison, since the runtime for each method depends differently on b. Here in the main text, primarily focus understanding how well each method performs within a fixed runtime budget (rather than fixed 6).
Comparing against MFC-Approx and MFC-OPT (Question 1). When b 0 (leftmost point in each plot), all MultiRepMFC algorithms correspond to the previous MFC-Approx algorithm. The output for each algorithm traces out a performance curve as b (and runtime) increases. These curves tend to decrease steeply at the beginning, showing that MultiRepMFF produces noticeably better spanning trees than MFC-Approx with only small amount of extra work. In many cases, the spanning tree quality gets very close to an optimal solution at a fraction of the time it takes to run MFC-OPT. One outlier in these results is the Names- dataset, where MFC-OPT is much faster than usual. This is because initial forests for Names-US are highly imbalanced, with one large component containing nearly all the points. For highly-imbalanced forests, it is much cheaper to optimally solve the MFC step. Running MultiRepMFC is therefore not useful for large values of b. Nevertheless, for small values of b, MultiRepMFF provides a meaningful interpolation between MFC-Approx and MFC-OPT.
Comparing methods for BESTREPS (Question 2). From the top row of Figure prisingly, the simplest method (ixed())-MutiRepMFF)) whose progress tends to plateau after a certain point. This may be because too myopic in assigning representatives. For example, it is possible that adding one extra represen- tative to certain component would change the objective very little, but adding two or more would significantly decrease the objective. (Mud(()-MuliiRepFF would be able to achieve this benefit for the right choice of é, whereas
that DP-MultiRepMFC tends to produce the best spanning trees within a fixed time budget. Perhaps sur-
tends to outperform StreddyMuutiiRepM/
is
may never notice the benefit.
Comparing a values (Question 3). Our bound a (second row of plots in Figure 3) is always very close to 1, and provides a much better bound to the true approximation ratio than the worst-case 2-approximation. This can be seen in the third row of plots Figure 3 This is significant since computing the true Cost Ratio is impractical, as it requires optimally solving MFC. However, a can be computed easily in the process of running MultiRepMFC, and therefore serves as a very good proxy for the true approximation ratio with virtually no extra effort. As a practical benefit, this opens up the possibility of choosing b dynamically in practice. In particular, one can choose to add representatives until achieving a satisfactory value of a, and only then MultiRepMFC.
Figure 3 also shows that different approaches for BESTREPS perform differently in terms of how While DP- DP-MultiRePPFC is slightly better than other methods in terms of
well they minimize Cost Ratio, it is far better at minimizing a. Again, this is significant because a is an approximation guarantee that we can efficiently obtain in practice, unlike the true Cost Ratio. Furthermore, as runtime increases, the gap between a and Cost Ratio shrinks more quickly for DP-MultiRepMFC than for other methods (Figure 3 third row). This provides further evidence for the benefits of the dynamic programming approach for BESTREPS, which helps further address Question 2.
5 CONCLUSIONS AND DISCUSSION
Metric forest completion is a augginntd framework for finding spanning tree in an arbi- trary metric space, when the learned input is an initial forest that serves as a starting point. We have introduced generalized approximation algorithm for this problem that comes with better theoretical approximation guarantees, which we prove are tight. Our results also include very good instance- specific approximation guarantees that overcome worst-case bounds. In numerical experiments, we show that with a small amount of extra work, we can obtain much better quality solutions for MFC than the prior approach. One open direction is to pursue approximations for metric MST in terms of other quality parameters (aside from y-overlap) for the initial forest. Another question is whether one achieve worst-case approximation factors below 2 for MFC, using alternative techniques with subquadratic complexity. Finally, an interesting question is whether we can prove general lower bounds on the approximation ratio that hold for all algorithms with subquadratic complexity.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
This work was performed under the auspices of the U.S. Department of Energy by Lawrence Liv- ermore National Laboratory under Contract DE-AC52-07NA27344 (1NN-C0NF-2011636)) and was supported by LLNL LDRD project 24-ERD-024.
REPRODUCIBILITY STATEMENT
Our code included in the paper supplement and also publicly available at /tttps:
com/tommy 9/Met r cF orest Comp ion This includes all source code for our algo- rithms, the commands that were run to produce the main results, and scripts for plotting our results. The output from our experiments is included in results folder, so that all plots from the main text can reproduced. Most of the datasets are too large to include the supplementary file, so we have included instructions in the supplement's README regarding where the original datasets can be obtained and how they were preprocessed. The appendix our paper also includes a description for each dataset and references to the original sources. For theoretical results, complete proof details are included either in the main text or the appendix.
REFERENCES
Pankaj K Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. Euclidean mini- mum spanning trees and bichromatic closest pairs. In Proceedings of the Symposium on Compu- tational Geometry, pp. 203-210, 1990.
Mahmood KM Almansoori, Andras Meszaros, and Miklos Telek. Fast and memory-efficient ap- proximate minimum spanning tree generation for large datasets. Arabian Journal for Science and Engineering, pp. 1-14, 2024.
Ilya Amburg, Nate Veldt, and Austin Benson. Clustering in graphs and hypergraphs with categorical edge labels. In Proceedings of The Web Conference, pp. 706-717. Association for Computing Machinery, 2020.
Sunil Arya and David Mount. fast and simple algorithm for computing approximate Euclidean minimum spanning trees. In Proceedings of the Symposium on Discrete Algorithms, pp. 1220- 1233. SIAM, 2016.
Ziyad Benomar and Vianney Perchet. Non-clairvoyant scheduling with partial predictions. In Inter- national Conference on Machine Learning, 2024.
Otakar Borûvka. O jistém problému minimálním. 1926.
Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, and Chen Wang.
Maximum Independent Set. Approximation, Randonization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024), 2024.
Vladimir Braverman, Jon C Ergun, Chen Wang, and Samson Zhou. aaamingg-augmened hierarchi- cal clustering. In International Conference Machine Learning, 2025.
Paul Callahan and S Rao Kosaraju. Faster algorithms for some geometric graph problems in higher dimensions. In Proceedings of the Symposium Discrete Algorithms, volume 93, pp. 291-300, 1993.
Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. New streaming algorithms for high dimensional EMD and MST. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pp. 222-233, 2022.
Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, and Erik Waingarten. Streaming Euclidean MST to a constant factor. In Proceedings of the Symposium on Theory of Computing, pp. 156-169 169. Association for Computing Machinery, 2023.

---

Published as a conference paper at ICLR 2026
Xinquan Chen. Clustering based on near neighbor graph and a grid cell graph. Journal of Intelli- gent Information Systems, 40:529-555 554, 2013.
Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. Predictive flows for faster Ford-Fulkerson. In International Conference on Machine Learning, pp. 7231-7248. PMLR, 2023.
Sami Davies, Sergei Vassilvitskii, and Yuyan Wang. Warm-starting push-relabel. Advances in
Neural Information Processing Systems, 2024.
T Z DeSantis, Hugenholtz, N Larsen, M Rojas, E L Brodie, K Keller, T Huber, D Dalevi, P Hu, and G L Andersen. Greengenes, a chimera-checked 16S rRNA gene database and workbench compatible with ARB. Appl Environ Microbiol, 72(7):506--5072, Jul 2006. ISSN 0099-2240 (Print); -996-5336 (Hlectronic); 0099-2240 (Linking). doi: 10.1128/ 20.112//AEM.00006--1
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Aidin Niaparast, and Sergei Vassilvitskii. Binary search with distributional predictions. In Advances in Neural Information Processing Systems, 2024.
Jon Ergun, Zhili Feng. Sandeep Silwal, David P Woodruff, and Samson Zhou. k-means clustering. Machine learning, 2022.
Marek Gagolewski, Anna Cena, Maciej Bartoszuk, and Lukasz Brzozowski. Clustering with mini- mum spanning trees: How good can it be? Journal of Classification, 42(1))90-112 1-990-122,-0 2025.
Teofilo F Gonzalez. Clustering minimize the maximum intercluster distance. Theoretical com- puter science, 38:293-306, 1985.
John C Gower and Gavin JS Ross. Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society: Series C (Applied Statistics), 18(1):54-64, 1969.
Junyu Huang, Qilong Feng, Ziyun Huang, Zhen Zhang, Jinhui Xu, and Jianxin Wang. New algo- rithms for the learning- augmented k-means problem. In The Thirteenth International Conference on Learning Representations, 2025.
Piotr Indyk. Sublinear time algorithms for metric space problems. In Proceedings of the Symposium on Theory of Computing, pp. 428-434, 1999.
Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong. Massively parallel algo- rithms for high-dimensional Euclidean minimum spanning tree. In Proceedings of the Symposium Discrete Algorithums, pp. 9960-39920 SIAM, 2024.
Jothi, Sraban Kumar Mohanty, and Aparajita Ojha. Fast approximate minimum spanning tree based clustering algorithm. Newrocomputing, 272:542-557, 2018.
Kaggle. What's
httpps:/www.kaggle..com http://whhtsccooonnngg 2015.
Joseph B Kruskal. On the shortest spanning subtree of graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1):48-555 -0,,880,11111 1956.
Riccardo La Grassa, Ignazio Gallo, and Nicola Landro. Ocmst: One-class novelty detection using convolutional neural network and minimum spanning trees. Pattern Recognition Letters, 155: 114-120, 2022.
Martine Labbé, Mercedes Landete, and Marina Leal. Dendrograms, minimum spanning trees and feature selection. European Journal of Operational Research, 308(2)5555-577, 2023.
Adam Lechowicz, Rik Sengupta, Bo Sun, Shahin Kamali, and Mohammad Hajiesmaili. Time fair- ness in online knapsack problems. In The Twelfth International Conference on Learning Repre- sentations, 2024.
Harry Loberman and Amold Weinberger. Formal procedures for connecting terminals with a mini- mum total wire length. Journal of the ACM (JACM), 4(4):428 437, 1957.
12

---

Published as a conference paper at ICLR 2026
William B March, Parikshit Ram, and Alexander G Gray. Fast Euclidean minimum spanning tree: algorithm, analysis, and applications. In Proceedings the SIGKDD international conference on the
Knowledge Discovery and Data mining, pp. 603 612, 2010.
Roy E Marsten and Thomas L Morin. A hybrid approach discrete mathematical programming. Mathematical programming, 14(1):21-40) 1978.
Samuel McCauley, Benjamin Moseley. Aidin Niaparast, Helia Niaparast, and Shikha Singh. Incre- mental approximate single-source shortest paths with predictions. In International Colloquium on Automala, Languages, and Programming (ICALP 2025), 2025.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65(7):33-355 2022.
Thy Nguyen, Anamay Chaturvedi, and Huy L Nguyen. Improved learning-augmenter algorithms for k-means and k-medians clustering. In International Conference on Learning Representations, 2023.
Adam Polak and Maksym Zub. Learning-augmenter maximum flow. Information Processing Let- ters, 186:106487, 2024.
Robert Clay Prim. Shortest connection networks and some generalizations. The Bell System Tech- nical Journal, 36(6): 1957.
Philippe Remy. Name dataset. httppp///atttuooooo////hlpppprrp datasst 2021.
Michael Ian Shamos and Dan Hoey. Closest-point problems. In Proceedings of the Symposium on Foundations of Computer Science, pp. 151-162. IEEE, 1975.
Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung Chan An. Improved soaming-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis. In In- ternational Conference on Machine Learning, pp. 31539-31561. PMLR, 2023.
CJ Stam, P Tewarie, E Van Dellen, ECW Van Straaten, A Hillebrand, and P Van Mieghem. The trees and the forest: characterization of complex brain networks with minimum spanning trees. International Journal of Psychophysiology, 92(3):129-138, 2014.
Pravin M Vaidya. Minimum spanning trees in k-dimensional space. SIAM Journal on Computing, 173):572-582, 1988.
Nate Veldt, Thomas Stanley, Benjamin W Priest, Trevor Steil, Keita Iwabuchi, TS Jayram, and Geoffrey Sanders. Approximate forest completion and learning-augment algorithms for metric minimum spanning trees. In International Conference on Machine Learning, 2025.
Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun. Fast parallel algorithms for Euclidean minimum spanning tree and hierarchical spatial clustering. In Proceedings of the International Conference on Management of Data, pp. 1995-1955, 2021.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmark- ing machine learning algorithms, 2017.
Caiming Zhong, Mikko Malinen, Duoqian Miao, and Pasi Fränti. fast minimum spanning tree algorithm based on k-means. Information Sciences, 295:1-17, 2015.
13

---

Published as a conference paper at ICLR 2026
Algorithm MullRRepMFC(R (R, E [t]}
1: Input: X (I1, 22,,,.,,, components
{Pi, P2...., . Pt), spanning trees
(Ti, Tt..2.... Tr}, nonempty R _ P3 for each E [t].
2: Output: Spanning tree for Gx = (X, Ex).
3: for (i,j) E (2) do
4: Wi-s mirr, d(z;,Ty)
5: Wj-i =
thi = PP, d(zy.Ti) Ti)
6:
7: end for
8: Tp = (f
9: Return spanning tree 7 obtained by combining E. with edges corresponding to Tp.
A ADDITIONAL MULTIREPMFC ALGORITHM DETAILS
This relies on a black-box function OptMST which computes an optimal solution for a minimum spanning tree for graph. This is specifically applicd to find an MST of the coarsened graph with respect to the new weight function w; Vp + R, which corresponds to set of edges in X' that completes the initial forest G2 = (X, E,). When for every E [t]. this corresponds to our previous MFC-Approx algorithm (Veldt et al,
Pseudocode for MultiRepMFC is given in Algorithm| 1
R3 2025).
Comparison between Theorem and prior work. Our proof that MFC-Approx a 2- approximation for MFC (and a 27-approximation for metric MST) simplifies our prior analy- sis (Veldt et al.] (025) in a few ways. The prior analysis relied on partitioning edges in the coarsened graph based on whether or not they were 3-bounded (meaning úhs S (wwt,) for some initially un- specified B > 1. The analysis then considered two other spanning trees of the coarsened graph that are optimal with respect to two other hypothetical weight functions that depend on B. This led to bounds for different parts of the weight of T (the returned by MFC-Approx), in terms different expressions involving B. The best approximation guarantee of 3 (3 + v5) /2 was obtained by solving quadratic equation resulting from the bounds.
In contrast, our new analysis completely avoids the need to partition edges based on an unknown 3, work with hypothetical weight functions, or solve for the best 3 in this way. Our analysis shares some other steps in common with our prior proof (Veldt et al. (025). but is ultimately able to apply basic facts about distances and triangle inequalities more directly. This leads to an analysis that is simpler, shorter, and tighter.
B DYNAMIC PROGRAMMING FOR REPRESENTATIVE ALLOCATION
Consider resource allocation problem of the form
minimize
A(((t))
(14)
subject
Σ bli =
(15)
No
(16)
where we assume the functions {f:: [t]] are given and
the convention that natural num-
bers include zeros: N = {0, 1,2, .. This matches Problem (13) in the main text after applying change of function fi()) (j + 1) better highlight that the goal is assign extra representa-
tives, beyond the first representative for each component. The following theorem guarantees that if
we can solve this problem, we can use obtain a 2-approximation for BESTREPS.
Theorem Let (b,: [t]] be the optimal solution to Problem 13). For E [t], define R; to be the first b; + 1 cluster centers chosen by running the greedy 2-approximation for k-center on P..
Then ( [R: i [[]] is 2-approximate solution for BESTREPS.
14

---

Published as a conference paper at ICLR 2026
Proof. BESTREPS is equivalent to minimizing Σi=1 (b; + subject to Ei= b, = and 6; for every i E [t]. Let {b; [ denote an optimal solution for this problem. The 2-approximation guarantee for {6g: E [d] the corresponding sets {R; foolowws from the fact that {6,} are optimal for the { functions, and the fact that (j) S 4(j) S ()) for every E [t] and
j E e 1|:
+1 E abb 1) E. & 1) S 2 G 1).
We can solve the problem in [4 using dynamic programming. For integers B E [0, bj and [t].
define S27 = (b E N Σ bld] = B} and define
F(T, B)
min
f.bii))
be
Our goal then is to efficiently compute F(t, b).
In the context of the BESTREPS problem, F(T, B) is the optimal way to assign B extra representa- that
tives to the first I" components, If there no extra representatives to assign,
F(T,0) Σ (())) for T E [t]. i=1
If there is only one component to assign extra representatives to, then we have
F(1, B) = (B) for B 0, l,...,b.
Observe next that the optimal way allocate B representatives across the first T components is found by considering all ways to optimally allocate l representatives to the first components, while allocating B -k representatives to the Tth component. This is captured by the formula:
F(T, = min F(T - k, + fr k))
OSksB
Using bottom-up up dynamic programming algorithm, computing F(T, B) when given F(T k)) and fr B k)) for every k E [0, B takes O(B) (b) time for every T < I. Since we need to compute F(T, B) for choices of T and b choices B, the overall runtime is (112).
In practice, we need to know not just the value of Ftt, b) but the choice of b E No that produces the optimal solution, since this determines the number of representatives for each component. We can accomplish this naively by storing vector of length-t for each choice of F(T, B), leading to memory requirement of (()b). In practice, we reduce this to ((b) by noting that F(T, B) only depends F(T 1, k) for l [0, BJ. Thus, long
the length-t vectors associated with F(T 1, k) for E [0, B), we can discard all length-t vectors associated with FJJ, k) for JK - and & [0, B).
Details on the use of LLMs for the BESTREPS results. Given the similarity between BESTREPS and the classical k-center problem, we prompted LLM to help check whether this problem had been previously studied. The LLM noted several other variants of k-center and similar resource al- location problems, but unable to find prior examples where this exact problem had been studied. algorithm for
The LLM then suggested a greedy algorithm that it claimed was a 2-approximati this problem, but the approximation analysis it provided was incorrect. With additional prompting, the LLM suggested a dynamic programming approach. Although the LLM's dynamic programming algorithm and its proof still contained minor errors, the general strategy matched the basic approach we ultimately used to prove 2-approximation. This is a natural strategy for an LLM to suggest, given that the dynamic programming approach is standard for variants of the knapsack problem and resource allocation problems in this form. See, for example, the work of Marsten & Morin 1978). which effectively covers the same strategy. LLMs were not used research ideation for any other aspects of the paper, and in particular LLMs were also not used to aid in the final write-up of results for REPTREPS, or for the write-up any other section of the paper.
not used for any of the design analysis in Section 3.1
15

---

Published as a conference paper at ICLR 2026
C DETAILS FOR ALGORITHM VARIANTS AND RUNTIMES
There are several nuances to consider when reporting runtimes for our algorithm variants DP- MultiRepMFF, Sreeed-MMltiRepMFFC and (Mee(())MutiRReMMF.. These all have different runtimes when addressing the BESTREPS problem, but in many cases those runtimes are overshadowed by the MultiRepMFC step that follows when approximating MFC. The relative difference between these algorithms can be further obscured if one also considers the time it takes to compute the initial forest. Although computing an initial forest is not part of the MFC problem, it is an important consideration if the ultimate goal is to approximate the original metric MST problem.
We provide a careful runtime comparison for each algorithm here, along with some considerations regarding the time to compute the initial forest. Let Qx denote the time for one distance query in X We assume the number of components in the initial forest is Onn) for some 8 E [0. 1), since the MFC framework only leads to subquadratic time algorithms if t is dominated by the number of points. We use Ô to hide logarithmic factors in n.
Runtimes for BESTREPS step. In order to find set of representatives R of size + t using the dynamic programming algorithm or the greedy method, we first must compute (()) for E [t] and j E [b 1]. To do so, we run the standard greedy 2-approximation for k-center on P: for each i [4] with A = b 1. This means k.. distance queries for i E [t] so this step takes O(bb 1)m time after summing over all i E [t].
Dynamic programming. The dynamic programming step takes an additional Otb²²) time to allocate representatives to components. The total time for approximating BESTREPS via dynamic program- ming is therefore O(b(b + 1)0x tb²).
Greedy representative allocation. The greedy algorithm for BESTREPS starts with (b1, b2,..., (0,0, 0, , 0). It then simply iterates through the number of additional representatives from 1 to b, and each step adds the 6; value that leads to the largest decrease in the objective Ei 0, + 1). More concretely, the algorithm must maintain the value of
......,,)) bb)
A (b; + (b; 2)
for each E [t), and choose the component with maximum A; each step. Observe that A, 2 for each [t] since ès is decreasing cost function. A simple O(tb)-time implementation is to store A, values an array and iterate through all values to find the maximum at each step. This can be improved to ( + b logg() i) time using a heap. However, in either case this step is dominated by the time to compute the 2, functions. So the runtime for the greedy algorithm for BESTREPS is O(n(b= + 1)0x).
Fixed(() M)MutiiePPFFFFC baseline. order to choose é b/t representatives per component (assum- ing is a multiple of t), simply run the greedy k-center 2-approximation each component with k = L. We then use the resulting centers as the representatives. This has a faster runtime for BESTREPS of ((EQQx).
Runtime for MultiRepMFC step. Fix a set (Ra : E [4]} of nonempty representative sets for the components. Let It = U R& where [R]] = 6 6++ t. Given this input, MultiRepMIF first computes the distance between each R2 and every x E X' P.. This is a total of
Σ [Ral . - [P]) < (b 1 l)n
distance queries, needed to define the weight function 인 for the coarsened graph. It then takes O log () time to find the MST of the coarsened graph with respect to w using Kruskal's algo- rithm. One could implement the latter step more quickly using alternate MST techniques, but our implementations apply Kruskal's 's since this is simple and is not the bottleneck of MultiRepMFC, neither in theory nor practice. Overall, running MultiRepMFC with a fixed takes O(n(b + t)Qx).
Full runtime analysis for MFC approximation algorithms. Although Greedy--ulliReMMFOO and MMMei((eeil differ in terms of their runtime for the BESTREPS step, both of these al- gorithms are asymptotically dominated by MultiRepMFC. Therefore, for MFC (i.e.. ignoring initial forest computation time) their runtime is O(n(b + t)Qx). DP- MultiRepMFC, the other hand, has runtime of (nn(b + t)2x + tb2) to account for the more
approximation algorithms
16

---

Published as a conference paper at ICLR 2026
accurate (but slower) dynamic programming strategy for allocating representatives. In cases where b is small enough (b = Onn/t)), this term is negligible asymptotically. Hence, when we have small budget for additional representatives, (note that Fixed(()MulliRpMMFG is not defined in this case). As b increases beyond this limit, still expect DP-MultiRepMFC to produce better spanning trees than its competitors when we consider fixed 6, but the runtimes are then not directly comparable.
would expect OP-MultiRepMFC to improve over
MFC- IFC-Approx and
Considerations for computing the initial forest. The runtime for computing an initial forest can vary significantly depending on the strategy used. In our prior work (Veldt et al. 2025) we computed initial forests by first running the greedy 2-approximation for k-center with is and then applying Kruskal's 's algorithm to find optimal MSTs of the components. In cases where the k-center step produces balanced clusters (which it often did in practice but not guaranteed to), this runs in O(ntQx + n²//t)-imme /tmme. In practice, we found that this was typically much faster than running an (2(n²) )2(me)-time )-time exact algorithm for MST, but was also usually the bottleneck for the MFC framework. In particular, for most values of t, computing an initial forest was slower than running MFC-Approx. Whether or not computing the initial forest is the most expensive step for finding an approximate spanning tree, this will have an impact on the comparison between DP-MultiRepMFC, and Fi MuuttReeFF. Especially in cases where computing initial forest step is expensive, the runtime differences between these algorithms for the MFC will be less important.
partition X,
Motivation for = v.. In our numerical experiments. we t = v since this roughly minimizes the asymptotic runtime when factoring in the initial forest computation. In more detail, consider simplified conditions where the initial k-center step produces balanced partitions, b = O(), and 2x O(log n.). If these conditions hold, the runtime for finding initial forest and running DP- MultiRepMFC (nt + 1 + n²² /t). This is minimized when & @(vr). If we instead used the runtime would be Ö(rl + n²/t) under these conditions, which is still minimized by / = @(vr). Even if these conditions do not all perfectly hold, we expect I = @(vn) to at least approximately minimize the runtime. We remark finally that there are other existing heuristics for computing an approximate MST that also rely on partitioning a dataset into t components and then connecting disjoint components. Using a similar arguments. these methods select t v in order to minimize the overall runtime (Jothi et al. 2018 Zhong
Greeddy-MutiRepMFC or Fixed(e)-MuliRepPPEE
et al. 2015).
Comparison with existing EMST algorithms. Although our main focus is to design spanning tree algorithms that work for arbitrary metric spaces, it is also useful to consider the guarantees of MultiRepMFC against existing techniques that work for the more restrictive Fuclidean minimum spanning tree problem (EMST). For this comparison, we consider d-dimensional vectors where d is a constant but potentially very large. Using the simplified analysis above, the runtime of MultiRepMFC scales roughly as n 1.5 by choosing = (v)R).
As noted above, there are several existing heuristics for EMST that partition the data into v compo- nents and then add additional edges to connect components before refining into an overall spanning tree (Jothi al., 2018 Zhong et al.] 2015). MultiRepMFFC has comparable asymptotic runtime to these methods, while also having the advantage of satisfying concrete theoretical guarantees.
Agarwal et al. 1990) showed that an optimal EMST can be computed in O(n" T time. A simple calculation shows that this is slower than O(n whenever d > 6. Thus, although it provides optimal solutions, is not expected to nearly as scalable as MultiRepMFC for even for modest values of d. Arya & Mount (2016) presented a method for computing (1 + =-approximmte EMST in time (n log n + + - log" !) if d is a constant. However, this runtime hides exponential factors in d of the form O(1)d, which likely be challenge for practical applications in situations where d is large, e.g., the FashionMNIST dataset where d = 784. In contrast, MultiRepMFC has no exponential dependence on d, and has no problems being run on FaShionMNIST and other high- dimensional Euclidean datasets.
There are many other theoretical and practical algorithms for EMSTs that have been designed under diverse computational models and assumptions (Chen et al., 2023 2022 March et al. (2010) Wang al.) |021 Jayaram al., 2024). The size of the literature complicates comprehensive com- parison. We expect that the best practical algorithms for EMSTs will outperform MultiRepMFC on
17

---

Published as a conference paper at ICLR 2026
Euclidean data, since they specialized to this setting and heavily leverage the assumption that the data is Euclidean. Nevertheless, MultiRepMFC also provides scalable approach that is also very simple to implement. Its most important feature is that it applies to arbitrary metrics.
D ADDITIONAL EXPERIMENTAL DETAILS
Our experiments are run on large research server with ITB of RAM with two 22-Core AMD pro- cessors. We use a subset of the datasets considered in ou prior work (Veldt et al. (005)) Specifically, we selected four datasets that correspond to different distance metrics. We summarize the datasets below, along with link the original data source(s). See our prior work (Veldt et al. 2025) for additional steps in preprocessing data from the original source.
Cooking (Jaccard distance) (Kgglle 2013 Amburg al. 2020p. Sets of food ingredients that define recipes. There are n 39, 774 recipes and 6714 ingredients.
FashinMNIST (Euclidean distance) (Xiao et al. 2017). Vectors of size d = 784 represent- ing flattened images of size 28 x 28 pixels, where each image is picture of a clothing item.
Names- US (Levenshtein edit distance) (Remy 2021
Each data point a string represent- The average name length is 6.67.
ing a last name of someone in the United States.
GreenGenes-aligned (Hamming distance) (DeSantis al., 2006). An alternate form for the GreenGenes dataset where sequences have been aligned that each is represented by a fixed length sequence of 7682 characters.
When performing experiments for the Cooking dataset, we repeatedly take uniform random order- ings of data points. Because our algorithms are deterministic, this random ordering effects only the arbitrary elements selected for the first center during the k-center step of the initial forest compu- tation, and the first representative chosen for each component when approximating the BESTREPS problem. For all other datasets, take uniform random samples of n 30, 000 data points. In all cases, we choose = In which equals 199 for Cooking and 173 for other datasets. all our plots, report the average performance over 16 different random samples. Although mation algorithms can scale to much larger sizes of n, we also run an exact algorithm for MFC for our comparisons, which can take O(n²) the worse case. We restrict values of for which we can find an optimal solution (and run all of our approximation algorithms for many different choices of i) within a reasonable amount of time.
approxi-
Budget choices and runtime differences. For each variant of MultiRepMFC, we used budgets b ranging from 38t increments of 2t. This means that for the largest budget, we considered having an average of 39 representatives per component. For Fixed MuuliFeeePFFCCCCCC this corresponds values from to 39 in increments
For a fixed budget b, DP-MuliRepMFC tends to take longer than Mulley. but for somewhat surprising reason. Although the time find representatives is slower for DP- MultiRepMFC, this constitutes only small fraction of the total runtime and is not the primary reason why DP-MultiRepMFC slower for fixed b. By checking runtime for different steps, we found that the increase in runtime for DP- OP-MultiRepMFC: is due primarily to the total time it takes to compute the distances between representatives and points outside each representative's component, when running MultiRepMFC. For fixed R, recall the number of distances computed by MultiRepMFC(R)) to find ú is
Σ [R-1- -P.))-
1=1
Although this is bounded above by (b (b+1)n, in practice this value will depend on which components the representatives are assigned to. In particular, if representative is contained in component P; that is very large, then (|x) PP.)) may be significantly smaller than the bound (²)). We found that the number of distances computed by DP-MultRReMFFC tends be much larger than the number of distances computed by
This suggests that Preedd--MuliRReMMFG may have a greater tendency to place representatives in large components, while DP RPPM finds ways to distribute representatives differently in a way that leads to better spanning trees but more distance computations.
18

---

Published as a conference paper at ICLR 2026
= Cost -1
20
10 3.
10"a
10
10:30
10a11
10
10
10
10-
10
10-10
200040006000
2000
4000
6000
0
2000
4000
6000
0
2000
4000
6000
Ea =0-1
10-23
10-
100
10-21-
10
10a
10-25
10:25
10 81
10:23
10
10"11
2000 40006000
2000
4000
0
2000
4000
6000
2000
4000
6000
a -Cost Ratio
10.2._
10.15.
10
10-21_
10.25
10.90_
10"23_
10-25_
10.92_
10
10
10"42
4000400060000
2000
4000
6000
0
2000
4000
6000
2000
4000
6000
Runtime
1200
2500
500
140
2000
800
1500
300
120
400
1000
200
100
500
2000
4000 6000
2000
4000 6000
2000
4000 6000
2000
4000 6000
b
b
b
(a) Cooking (Jaccard)
(b) GrGenes (Hamming)
(c) Fashion (Euclidean)
(d) Names (Levenshtein)
Dynamic
Fixed
Greedy
Figure 4: We display the performance of each variant of MultiRepMFC as budget increases. Each point corresponds running one method with fixed budget b.
Additional experimental results. In Figure we display results for Cost Ratio 1, a 1, and the gap between these two values as b varies. These plots show the same basic trends as Figure [3 and the curves are more clearly aligned since there is exactly one point per value of b. We also display runtimes, as these differ for each method for each fixed choice of b.
Recall that the MFC Cost Ratio is defined by
wx wx(M) + wx (E,)
W x ( + + wx( (Ea)
where M is the set of new edges added by MultiRepMFC, M is the set of new edges added by an optimal solution to MFC, and E, is the initial forest. As another interesting point of comparison, Figure 5 displays results for the Completion Ratio, which only considers the weight of new edges, and does not incorporate the initial forest weight:
W. (x
wxx (M*)
We previously showed that not possible design an algorithm with subquadratic complexity that comes with an a priori upper bound on this ratio in general metric spaces (Veldt et al.) 2025). However, is a useful quality measure to consider empirically, since focuses more directly on the new edges found by the algorithm (recall that the weight of the initial forest is constant for every feasible solution for MFC). F shows that adding even a small number of extra representatives improves the Completion Ratio even more significantly than the improvement to the MFC Cost Ratio. This indicates that MultiRepMFC is generally able to find much smaller edges to connect components in the initial forest. This is promising sign for downstream applications where it especially important to find small weight edges to connect components. For example, a key motivating application is cluster dataset X' by mining dendrogram associated with spanning
19

---

Published as a conference paper at ICLR 2026
Completion Ratio
1.9
Completion Ratio
Completion Ratio
Completion Ratio
1.7-
1.3
1.2
1.15
1.5-
1.2
1.10
1.3
1.1-
1.05
1.1
1.0
1.00
2000
4000 6000
2000
4000
6000
2000
4000
6000
2000
4000
6000
b
b
b
(a) Cooking (Jaccard)
GrGenes (Hamming)
Fashion (Buclidean)
(d) Names (Lovenshtein)
Dynamic
Fixed
Greedy
Figure 5: For each dataset, we display the completion ratio: the weight of new edges added by MultiRepMFC, divided by the weight of the new edges added by an optimal solution for MFC. Adding small number of extra representatives leads to an even more dramatic improvement to completion ratio than to the MFC Cost ratio.
tree for Gx. In this context, the initial forest provides a crude initial clustering of the data that can be refined and improved if one able truly find small weight edges between these initial clusters. The comparison between (xM) and wx (M*) is then especially important, even if the weight of the initial forest x E,) is large.
Finally, in Table I we provide closer look at the various performance metrics (e, Eas number of distance calls, Completion Ratio, and runtime) for three choices of b, on all datasets.
20

---

Published as a conference paper at ICLR 2026
Table 1: We give exact performance values for each variant of MultiRepMFO for three different values of Comp is the completion ratio, DC is millions of distance calls made by the entire pipeline, and RT is the runtime of the entire pipeline seconds.
RT
248.6
236.6
206.0
108. 7
108.6
82.1
96.6
93.5
94.0
506.0
506. 1
421.3
DC
150.6
133.9
118.7
104.8
104.8
84.1
458.6
443.8
437.8
120.2
120.1
99.5
b = 2t
Comp
1.56
1.68
1.62
1.15
1.18
1.20
1.01
1.06
1.05
1.10
1.10
1.10
0.0054
0.0068
0.0068
0.0071
0.0084
0.0094
0.0038
0.0209
0.0163
0.0196
0.0221
0.0257
E
0.0014
0.0017
0.0016
0.0009
0.0010
0.0012
0.0004
0.0019
0.0016
0.0020
0.0019
0.0020
RT
174.0
179.3
150.5
82.4
82.4
69.0
92.7
91.7
91.2
388.2
388.3
346.1
DC
104.3
102.9
88.4
75.1
75.1
64.8
437.2
432.9
426.9
91.0
91.0
80.7
Comp
1.67
1.71
1.69
1.19
1.21
1.23
1.05
1.08
1.09
1.18
1.18
1.18
b=
0.0060
0.0068
0.0071
0.0086
0.0097
0.0108
0.0116
0.0209
0.0241
0.0257
0.0280
0.0318
&
0.0017
0.0018
0.0018
0.0011
0.0012
0.0013
0.0015
0.0025
0.0027
0.0034
0.0034
0.0034
RT
99.8
99.6
100.0
56.3
56.3
56.4
88.4
88.4
88.4
270.1
270.2
270.5
DC
58.0
58.0
58.0
45.5
45.5
45.5
415.9
415.9
415.9
61.9
61.9
61.9
Comp
1.85
1.85
1.85
1.29
1.29
1.29
1.20
1.20
1.20
1.44
1.44
1.44
0.0075
0.0075
0.0075
0.0134
0.0134
0.0134
0.0408
0.0408
0.0408
0.0455
0.0455
0.0455
Ex
DP 0.0022
0.0022
0.0022
0.0017
0.0017
0.0017
0.0061
0.0061
0.0061
DP 0.0084
0.0084
0.0084
Alg
Greedy
Fixed
DP
Greedy
Fixed
DP
Greedy
Fixed
Greedy
Fixed
Dataset
Cooking
Fashion
Names
GG
21


Reviews:
[{"review_id": "wl0GPCLavL", "reviewer": "Reviewer_YEtK", "summary": "The paper considers the learning augmented minimum spanning tree (MST) problem for points in metric space. The authors propose solving this using the metric forest completion problem (MFC), where given an input of forest, goal is to find edges to form a full spanning tree, where the forest can be considered to be provided by an oracle (the learning augmented model). Previous work shows $\\Omega(n^2)$ runtime is necessary for optimally solving MFC, and gives a 2.62 approximate algorithm. This works extends the previous algorithm and obtains 2 approximation for MFC and $(2\\gamma + 1)$-approximation for learning augmented MST, where $\\gamma$ measures how good the input forest is w.r.t optimal MST.", "questions": "Can the authors provide hard instance for choosing multiple points arbitrarily per partition and the best possible approximation ratio for this?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The previous work solved the MFC problem by considering one representative point per partition (in the forest), and then finding the set of edges minimizing the cost. The extension in this work is to instead consider multiple points in each partition. The problem of finding the best such set of points across different partitions is formulated as a variant of the $k-$center problem. The authors then show an extension of the classical 2 approximation $k-$center algorithm for this problem. This in turn, helps improve the approximation ratio to 2. Experiments show a few additional representatives help obtain much better solutions.", "weaknesses": "The idea of using multiple representatives per partition is a natural one. The analysis is clean but the algorithmic contributions are incremental. The authors argue for tightness of their result, but in the hard instance, the number of representative points per partition is 1.", "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": "XfCeEVylB7", "reviewer": "Reviewer_sJB9", "summary": "The paper considers MST with far fewer than $n^2$ distance queries via the Metric Forest Completion framework, generalizing the one-representative scheme to MultiRepMFC (multiple reps per component) and considering only edges touching reps; it proves an instance-specific bound $\\alpha=1+\\mathrm{cost}(P,R)/w(E_t)$, yielding an $\\alpha$-approx for MFC and $\\alpha\\cdot \\gamma$-approx for MST, which in particular improves the classic one-rep worst case from 2.62 to 2 for MFC and $(2\\gamma+1)$ to $2\\gamma$ for MST with a matching tight example; representatives are chosen via a shared-budget multi-instance $k$-center with a 2-approx.", "questions": "Are there conditional lower bounds (e.g., SETH-style or decision-tree/query-complexity) for achieving <2 for MFC with $o(n^2)$ queries?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Firstly, I appreciate that the paper is well-written and well-organized; I enjoy reading it. The authors provide sufficient intuition for each main theorem, making it easy to understand the main idea behind the improved algorithm.\n\n2. This paper considers an interesting problem and uses a simple idea to get an improved algorithm. The algorithm is easy to implement, and thus, I expect it to have a positive impact in practice.\n\n3. Casting representative selection as a shared-budget multi-instance k-center and giving a 2-approx (Gonzalez curves + DP allocation) is neat. This algorithm is simple but looks interesting to me, and it may be helpful for other related problems.", "weaknesses": "1. From the theoretical view, this work looks incremental. The idea of increasing the size of the representative set is standard and appears in many other classical problems (e.g., k-means++ and greedy k-means++). This is a weakness from a purely technical angle, but borrowing techniques from one problem to create a better approximation algorithm sounds like a good approach to me, especially for a non-theory conference.\n\n2. Computing this larger representative set looks time-expensive to me, but the final running time is still in subquadratic time. Since several subquadratic Euclidean MST methods exist, a brief comparison explaining when your algorithm, MultiRepMFC, is preferable would help situate the work. I think it would be better to have a small table to compare distance query counts per algorithm variant or compare their precise running times.", "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": "6m2E8Rr1u8", "reviewer": "Reviewer_BGHP", "summary": "This paper considers a learning-augmented variant of the classical metric minimum spanning tree (MST) problem. The authors study a setting proposed by Veldt et al. (2025), where the algorithm has a-priori access to an initial forest with the goal to augment the initial forest to a spanning tree with the objective of minimising the total edge weight. This problem is called metric forest completion (MFC). Since both MST and MFC are known to require a running time of $\\Omega(n^2)$, the goal is to find approximation algorithms with a lower running time. The initial forest can be interpreted as a prediction of an MST, making MFC a learning-augmented problem. If there exists an MST that contains the initial forest, then optimally augmenting the initial forest leads to the computation of an MST. In general, the authors define a function $\\gamma$ which measures \"how close\" the initial forest is to being augmentable into an MST.\n\nAs a main result, the authors give a $2$-approximation for a MFC, which implies a $2\\gamma$-approximation for MST, with running time $o(n^2)$ if the number of components in the initial forest is $o(n)$. The algorithm is a generalisation of the algorithm by Veldt et al., which arbitrarily choses one representative from each component of the initial forest and finds the optimal augmentation that only uses edges incident to at least one representative. If the number of components is $o(n)$, then this algorithm yields a running time $o(n^2)$. The algorithm in this paper is based on the same idea but allows multiple representatives per component within a certain budget. As a first main result, the authors show that the algorithm is a $2$-approximation for a MFC and a $2\\gamma$-approximation for MST, for a fixed arbitrary set of representatives.  This improves upon the guarantees of $2.62$ and $2\\gamma+1$ by Veldt et al. As the second main result, the authors give a $2$-approximation for the problem of selecting the optimal set of representatives.This approximation first computes $b+1$ (the overall budget for representatives) potential representatives for each component by greedily solving $k$-center clustering instances. Then, it uses a knapsack DP to allocate the budget to the components. Finally, the authors give empirical experiments to compare the performance of the algorithm for different representative budgets and different representative selection methods.", "questions": "* Do you think there is hope for theoretical results that quantify the impact of allowing a larger budget for representatives?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The proof of Theorem 1 is very clear and simple, and at the same time improves the guarantees by Veldt et al. In my opinion, this is a very nice contribution.\n* The empirical experiments nicely illustrate how the choices (budget, selection of representatives) in the algorithmic framework impact performance of the algorithm.\n* The paper studies a well-motivated problem. The framework of learning-augmented algorithms is still mainly studied for online problems: According to the online repository, there are more than 170 paper studying online problems and only 30 studying running time improvements. Further work on learning-augmented settings to improve running times is an important contribution.", "weaknesses": "* The impact of allowing more representatives seems to be mainly studied empirically. It would be nice to have a discussion of theoretical results depending on the budget.\n* The new analysis of the algorithm does not require many new technical ideas.\n* For the sake of transparency, it would be nice to already mention in the introduction that the running time depends on the number of components.", "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": "k65HLQ2v65", "reviewer": "Reviewer_VpQA", "summary": "This submission deals with the problem of computing an approximate minimum spanning tree (MST) in subquadratic time when a partial solution is already given. More precisely, we are given a metric instance of the MST problem and an initial forest. The goal is to compute approximately a minimum spanning tree in subquadratic time among all spanning trees that contain the given forest. This problem is known as the metric forest completion (MFC) problem and it is motivated in the context of learning-augmented algorithms in which, e.g., a learning algorithm provides already a partial prediction for the minimum spanning tree.\n\nThe submission is heavily based on the research by Veldt et al. (2025), who first considered the MFC problem. The quality of the initial forest is measured by a parameter γ, which corresponds to the overlap of the given initial forest with some MST and is defined as the ratio between the current weight of the given forest and an optimal choice of an optimal minimum spanning tree, where we only count the weight of edges if the corresponding endpoints are in the same component as in the given forest (γ=1 means an optimal overlap with some MST). Veldt et al. gave a 2.62-approximation for MFC and showed that if the initial forest has a γ-overlap then the final spanning tree is a (2γ+1)-approximation of an MST. They also conducted multiple experiments and concluded that even simple heuristics for the initial forest provide very good results on synthetic and real datasets.\n\nAs first main contribution, the paper at hand improves on the theoretical bounds by showing that the algorithm by Veldt et al. (2025) even achieves a 2-approximation for the MFC problem and a 2γ-approximation for the metric MST problem. Additionally, it is shown that these bounds are tight in the worst case by designing a family of instances with γ=1, where for a specific choice of representatives in each component of the initial forest the ratio between the MST and the optimal corresponding MFC solution approaches 2 in the limit. The second main contribution is a modification of the algorithm by Veldt et al. (2025). While the latter is based on choosing a single representative for each component of the initial forest, the generalized version considered in this submission, is allowed to choose multiple representatives in each component, where the total number of additional representatives is upper bounded by some value b. For this setting (called best representatives problem) the authors design a 2-approximation using a 2-approximation algorithm for k-center and dynamic programming. Additionally, they test their algorithms on some of the real-world instances used by Veldt et al. and show experimentally that slightly increasing the number of allowed representatives gives some improvement in solution quality with only a small increase in runtime.\n\nThe paper is generally well written and follows closely the notation and experimental setup of Veldt et al. The theoretical results are clearly written. The proof of the 2-approximation is similar to the proof ideas by Veldt et al., but uses a different technique to bound the final cost and show the corresponding approximation factors. Allowing more representatives in each component is a natural extension of the algorithm. The experimental results show a slight improvement in solution cost when using more representatives per component or allowing for a larger additional time budget beyond the initial case with having a single representative.", "questions": "- The experimental section misses some additional information about the system on which the experiments were run. \n\n- Additionally, the significance of including additional representatives with respect to the runtime is not clear. For example, on the Cooking dataset it seems that the standard algorithm (b=0) did run in the experiments in approximately 100 seconds while the additional variants for selecting additional representatives can take more than 1000 seconds while improving the approximation factor only slightly. The improvement looks more severe due to the scaling and truncation of the diagram but if I understand Figure 2 correctly then already the original algorithm achieves an approximation factor of around 1,01. A summary in form of a table and different values of b could be useful here. \n\n- Also, in the experimental evaluation it is not exactly clear how the setup is precisely done, as the value b is not part of the description but only implicitly mentioned as being an effect of increasing values of b. I would have preferred an analysis as in the appendix, section E, where the value of b gradually increases, or even an additional plot with b on the x-axis and the corresponding runtime (increase) on the y-axis.\n\n- In Figure 2, for some of the greedy plots we have at some point straight lines, though b increases. Though the explanation, written in the section regarding question 2 is also making sense, I am still surprised that no further decrease in cost is being observed, even if much more representatives are allowed and costs are greedily decreased.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors improve the analysis of the existing approximation algorithm for the MCF problem and show tight bounds. The theoretical analysis is sound and the writing is good. The modified algorithm using additional representatives performs well in experiments.", "weaknesses": "The theoretical considerations rely very much on the work of Veldt et al. (2025) and neither the problem nor the algorithm is new. The extension towards additional representatives is quite canonical and does not provide better theoretical bounds. I have the impression that the results are slightly overstated: More representatives lead to better solutions but the difference seems to be rather small while the running time increases by a significant factor (see questions for more details).", "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": "kDuHP1liv7", "reviewer": "Reviewer_wWKo", "summary": "The submission improves upon the recent learning-augmented algorithm of Veldt, Stanley, Priest, Steil, Iwabuchi, Jayram and Sanders. It provides a tighter analysis which explains the previous gap between theoretical lower bounds and experimental performance, and also develops a related means of interpolating between slower approaches (with worst-case guarantees) and approximation.", "questions": "On page 1, the submission attempts to provide a more formal footing for learning-augmented algorithms as follows:\n\n\"The goal (of learning-augmented algorithms) is to design an algorithm that is consistent, meaning that it produces near-optimal outputs when the prediction is good, and robust, meaning that it recovers the same worst-case guarantees as a prediction-free algorithm when the prediction is bad\"\n\nHowever, isn't it the case that *every* procedure which is \"consistent\" can be made \"robust\" by simply running the algorithm achieving worst-case running time in parallel? After all, worst-case guarantees are typically provided in O-notation (and this also holds for the lower bounds for MinTSP provided by (Indyk 1999)), so a factor-2 decrease in the running time is still tight w.r.t. the worst-case lower bound. If the above is indeed a gap, please suggest an alternative formulation of the goal of learning-augmented algorithms - would it simply be achieving the \"consistency\" property?\n\nAdditionally, the description of the purpose of the experiments in the Introduction was a bit unclear to me. Based on my current understanding, they demonstrate that the \"novel\" DP you develop towards achieving your theoretical guarantees also outperforms greedy/trivial solutions in practice, but feel free to comment on (and potentially correct) this.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The contributions are, as a whole, clearly articulated and nicely presented. The submission's contributions are relevant for Machine Learning research and provide a nice combination of theoretical results supported with auxiliary experiments. The results are non-trivial. Moreover, the submission is nicely written overall.\n\nWhile not a strength per se, I found the openness and detail in which the authors discussed their use of LLMs refreshing.", "weaknesses": "The contributions could be seen as slightly incremental over the recent work of Veidt: the additional contributions \"on top\" of Veidt are not that novel/substantial (this applies in particular to Subsection 3.1). On the other hand, the motivation for the theoretical contributions of Subsection 3.2 and the experiments in Section 4 is weaker than for the improved bounds; these show that one can interpolate between the exact and approximate procedures by obtaining larger representative sets R (via a DP with approximation guarantees), which is not that surprising. \n\nI view both of the above as \"minor\" since in both respects, the submission only seems to be slightly below what I would consider the average for a combined theory+experimental ICLR paper.\n\n*Typos and Minor Suggestions*\n\n-Top of page 6: use \\qedhere to place qed in correct location.\n\n-Page 2: \"approximations factors\" ->  \"approximation factors\"\n\n-Page 2: \"... a disjoint set of trees called the initial forest, such that each of the n points belongs to one component in the forest.\" This sentence is unclear, as it does not specify what are the vertices of the forest. The formalization on page 3 is clear, however.\n\n-Page 6: \"This methods\" -> \"This method\"", "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)