Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
This work provides incremental improvements to algorithms for computational geometry and optimization problems, benefiting researchers and practitioners in areas like network design and machine learning.
The paper tackles the problem of improving learning-augmented algorithms for approximate minimum spanning trees in metric spaces by generalizing a prior method based on metric forest completion, achieving improved approximation factors from 2.62 to 2 for MFC and from (2γ+1) to 2γ for metric MST, with tight worst-case bounds and better instance-specific results.
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 $Ω(n^2)$ 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 $γ\geq 1$ is a quality parameter for the initial forest. We introduce a generalized method that interpolates between this prior algorithm and an optimal $Ω(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γ+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.