用近似补全树结构，加速度量空间下的最小生成树计算。
Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
- 先用启发式方法构建森林，再以低权重边连接成树。
- 提出2.62倍近似算法，可在亚二次时间内完成。
- 若初始森林与最优解重叠度高，则速度更快，适合实际应用。
在任意度量空间中寻找n个点的最小生成树（MST）是层次聚类及诸多机器学习任务的基础，但即使近似也需Ω(n²)时间。本文提出一种度量空间下MST的新框架：首先利用实用启发式方法获得一组不连通的连通分量构成的森林；然后寻找一组权重较小的边，将这些分量连接成一棵生成树。我们证明，即使第二步最优求解仍需Ω(n²)时间，但本文给出一个2.62-近似子二次时间算法。基于学习增强算法思想，若第一步得到的森林与最优MST有足够重叠，则可实现子二次时间近似，其近似比依赖于重叠程度。实验表明，在多种度量空间下，该方法能高效获得近乎最优的生成树，相比精确算法提速数个数量级。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。