The Central Spanning Tree Problem

跨度树是许多数据分析任务中的重要基本结构，当需要用“骨架”来概括数据集，或者需要树形图来处理下游任务时，就需要跨度树。流行的跨度树定义包括最小生成树和最优距离跨度树，即最小路由成本树。当寻找最短跨度树但允许额外的分支点时，甚至可以实现更短的跨度树：斯坦纳树。不幸的是，无论是最小生成树还是斯坦纳树都不太能抵抗观测中的噪声；也就是说，对原始数据集的小扰动经常导致相关跨度树的剧烈变化。作为回应，我们在数据处于欧几里得空间时做了两个贡献：在理论方面，我们引入了一个新的优化问题，“（分支）中心跨度树”，它包含了所有先前提到的定义作为特殊情况。在实践方面，我们经验证明，（分支）中心跨度树对数据中的噪声更具有鲁棒性，因此更适合用于用“骨架”来概括数据集。我们还提出了一种启发式方法来解决NP难的优化问题，并展示了它在生物学中的单细胞RNA表达数据和植物的三维点云上的应用。

论文旨在解决数据集中噪声对生成树算法的影响问题，并提出了一种新的优化问题——中心生成树，以更好地概括数据集的骨架。

中心生成树是一种更加鲁棒的生成树算法，可以更好地应对数据集中的噪声。论文提出了一个新的优化问题，将之前的生成树定义作为特例，解决了中心生成树的求解问题。

论文使用了单细胞RNA表达数据和植物三维点云数据进行实验，证明中心生成树算法相比传统算法更加鲁棒。论文还提出了一个启发式算法来解决NP难的优化问题，并且代码已经开源。

相关研究包括最小生成树、最优距离生成树和Steiner树等传统生成树算法，以及其他对生成树算法的鲁棒性进行研究的论文，如“Robustness of Minimum Spanning Trees in Weighted Graphs”和“Robust Minimum Spanning Tree in High Dimensions”等。