Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees

Nate Veldt, Thomas Stanley, Benjamin W Priest, Trevor Steil, Keita Iwabuchi, T.S. Jayram, Geoffrey Sanders
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:61126-61149, 2025.

Abstract

Finding a minimum spanning tree (MST) for $n$ points in an arbitrary metric space is a fundamental primitive for hierarchical clustering and many other ML tasks, but this takes $\Omega(n^2)$ time to even approximate. We introduce a framework for metric MSTs that first (1) finds a forest of trees using practical heuristics, and then (2) finds a small weight set of edges to connect disjoint components in the forest into a spanning tree. We prove that optimally solving step (2) still takes $\Omega(n^2)$ time, but we provide a subquadratic 2.62-approximation algorithm. In the spirit of learning-augmented algorithms, we then show that if the heuristic forest found in step (1) overlaps with an optimal MST, we can approximate the original MST problem in subquadratic time, where the approximation factor depends on a measure of overlap. In practice, we find nearly optimal spanning trees for a wide range of metrics, while being orders of magnitude faster than exact algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-veldt25a, title = {Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees}, author = {Veldt, Nate and Stanley, Thomas and Priest, Benjamin W and Steil, Trevor and Iwabuchi, Keita and Jayram, T.S. and Sanders, Geoffrey}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {61126--61149}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/veldt25a/veldt25a.pdf}, url = {https://proceedings.mlr.press/v267/veldt25a.html}, abstract = {Finding a minimum spanning tree (MST) for $n$ points in an arbitrary metric space is a fundamental primitive for hierarchical clustering and many other ML tasks, but this takes $\Omega(n^2)$ time to even approximate. We introduce a framework for metric MSTs that first (1) finds a forest of trees using practical heuristics, and then (2) finds a small weight set of edges to connect disjoint components in the forest into a spanning tree. We prove that optimally solving step (2) still takes $\Omega(n^2)$ time, but we provide a subquadratic 2.62-approximation algorithm. In the spirit of learning-augmented algorithms, we then show that if the heuristic forest found in step (1) overlaps with an optimal MST, we can approximate the original MST problem in subquadratic time, where the approximation factor depends on a measure of overlap. In practice, we find nearly optimal spanning trees for a wide range of metrics, while being orders of magnitude faster than exact algorithms.} }
Endnote
%0 Conference Paper %T Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees %A Nate Veldt %A Thomas Stanley %A Benjamin W Priest %A Trevor Steil %A Keita Iwabuchi %A T.S. Jayram %A Geoffrey Sanders %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-veldt25a %I PMLR %P 61126--61149 %U https://proceedings.mlr.press/v267/veldt25a.html %V 267 %X Finding a minimum spanning tree (MST) for $n$ points in an arbitrary metric space is a fundamental primitive for hierarchical clustering and many other ML tasks, but this takes $\Omega(n^2)$ time to even approximate. We introduce a framework for metric MSTs that first (1) finds a forest of trees using practical heuristics, and then (2) finds a small weight set of edges to connect disjoint components in the forest into a spanning tree. We prove that optimally solving step (2) still takes $\Omega(n^2)$ time, but we provide a subquadratic 2.62-approximation algorithm. In the spirit of learning-augmented algorithms, we then show that if the heuristic forest found in step (1) overlaps with an optimal MST, we can approximate the original MST problem in subquadratic time, where the approximation factor depends on a measure of overlap. In practice, we find nearly optimal spanning trees for a wide range of metrics, while being orders of magnitude faster than exact algorithms.
APA
Veldt, N., Stanley, T., Priest, B.W., Steil, T., Iwabuchi, K., Jayram, T. & Sanders, G.. (2025). Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:61126-61149 Available from https://proceedings.mlr.press/v267/veldt25a.html.

Related Material