Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915158427697152 |
|---|---|
| author | Veldt, Nate Stanley, Thomas Priest, Benjamin W. Steil, Trevor Iwabuchi, Keita Jayram, T. S. Sanders, Geoffrey |
| author_facet | Veldt, Nate Stanley, Thomas Priest, Benjamin W. Steil, Trevor Iwabuchi, Keita Jayram, T. S. Sanders, Geoffrey |
| contents | 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 $Ω(n^2)$ time to even approximate. We introduce a framework for metric MSTs that first (1) finds a forest of disconnected components using practical heuristics, and then (2) finds a small weight set of edges to connect disjoint components of the forest into a spanning tree. We prove that optimally solving the second step still takes $Ω(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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_12993 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees Veldt, Nate Stanley, Thomas Priest, Benjamin W. Steil, Trevor Iwabuchi, Keita Jayram, T. S. Sanders, Geoffrey Data Structures and Algorithms Discrete Mathematics Machine Learning 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 $Ω(n^2)$ time to even approximate. We introduce a framework for metric MSTs that first (1) finds a forest of disconnected components using practical heuristics, and then (2) finds a small weight set of edges to connect disjoint components of the forest into a spanning tree. We prove that optimally solving the second step still takes $Ω(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 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. |
| title | Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees |
| topic | Data Structures and Algorithms Discrete Mathematics Machine Learning |
| url | https://arxiv.org/abs/2502.12993 |