通过选择代表性点优化最小生成树计算，显著提升效率与精度。
Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
- 基于代表性点选择策略，只考虑关键边以加速算法。
- 将最小生成树近似比从2.62降至2，原问题从(2γ+1)降至2γ。
- 理论严谨且实验充分，适合算法设计与图学习研究者参考。
本文提出改进的学习增强型算法，用于在任意度量空间中寻找近似最小生成树（MST）。基于最近提出的度量森林补全（MFC）框架，该框架要求对给定的森林添加边以形成完整生成树。Veldt等（2025）证明最优补全需Ω(n²)时间，但设计了复杂度低于二次的2.62-近似算法；该方法对原始MST问题提供(2γ+1)-近似，其中γ≥1为初始森林质量参数。我们提出一种广义方法，介于此前算法与最优Ω(n²) MFC算法之间，仅考虑连接逐步选取的‘代表性’点的边。分析表明，可将MFC近似比改进至2，原始问题近似比降至2γ，且该结果在最坏情况下紧致。尽管如此，本方法仍能在具体实例中获得更优近似。我们还进行了全面的实验评估。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。