# Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion

arXiv: https://arxiv.org/abs/2602.24232 · HTML: https://mlsanity.com/paper/2602.24232/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 46 references that are in the map.
- First posted on arXiv 27 Feb 2026.

## Builds on (most cited first, 21 of 21)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Clustering in graphs and hypergraphs with categorical edge labels](https://mlsanity.com/paper/1910.09943/) (2019)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Predictive Flows for Faster Ford-Fulkerson](https://mlsanity.com/paper/2303.00837/) (2023)
- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [Learning-Augmented Maximum Flow](https://mlsanity.com/paper/2207.12911/) (2022)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Binary Search with Distributional Predictions](https://mlsanity.com/paper/2411.16030/) (2024)
- [Improved Learning-augmented Algorithms for k-means and k-medians Clustering](https://mlsanity.com/paper/2210.17028/) (2022)
- [Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering](https://mlsanity.com/paper/2104.01126/) (2021)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Learning-Augmented Hierarchical Clustering](https://mlsanity.com/paper/2506.05495/) (2025)
- [New Streaming Algorithms for High Dimensional EMD and MST](https://mlsanity.com/paper/2111.03528/) (2021)
- [Clustering with minimum spanning trees: How good can it be?](https://mlsanity.com/paper/2303.05679/) (2023)
- [OCmst: One-class Novelty Detection using Convolutional Neural Network and Minimum Spanning Trees](https://mlsanity.com/paper/2003.13524/) (2020)
- [Time Fairness in Online Knapsack Problems](https://mlsanity.com/paper/2305.13293/) (2023)
- [Incremental Approximate Single-Source Shortest Paths with Predictions](https://mlsanity.com/paper/2502.08125/) (2025)
- [Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree](https://mlsanity.com/paper/2308.00503/) (2023)
- [Warm-starting Push-Relabel](https://mlsanity.com/paper/2405.18568/) (2024)
- [Streaming Euclidean MST to a Constant Factor](https://mlsanity.com/paper/2212.06546/) (2022)

## Abstract (arXiv)

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(n2) time, but designed a 2.62-approximation for MFC with subquadratic complexity. The same method is a (2γ + 1)-approximation for the original MST problem, where γ ≥ 1 is a quality parameter for the initial forest. We introduce a generalized method that interpolates between this prior algorithm and an optimal Omega(n2)-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γ+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 a thorough experimental evaluation.