中央生成树问题

Apr, 2024

The Central Spanning Tree Problem

Enrique Fita Sanmartín, Christoph Schnörr, Fred A. Hamprecht

TL;DR基于欧几里得空间中的数据，本研究提出了一个新的优化问题 ——“（分支）中心生成树”，它包含了之前提到的所有定义作为特例，并从理论和实践两个方面证明了（分支）中心生成树相对于数据中的噪声更具鲁棒性，并更适合以其骨架来总结数据集。此外，本研究还提出了一种应对 NP 难优化问题的启发式方法，并在生物学的单细胞 RNA 表达数据和植物的 3D 点云数据上进行了展示。

Abstract

spanning trees are an important primitive in many data analysis tasks, when a data set needs to be summarized in terms of its "skeleton", or when a tree-shaped graph over all observations is required for downstre

spanning trees data analysis optimization problem robustness single cell rna

发现论文，激发创造

符号回归中最优生成树重建

研究论文探讨回归模型生成的问题，模型是原始函数的叠加，模型结构通过加权着色图描述，每个图顶点对应于某个原始函数，边赋予两个函数的叠加，边的权重等于叠加的概率，为了生成一个最优模型，需要从图邻接矩阵中重构其结构，所提出的算法从加权着色图重构最小生成树，本文提出了一种基于奖励收集斯坦纳树算法的新颖解决方案，并与其替代方案进行比较。

Jun, 2024

基于树嵌入的受限跳数网络设计

通过使用 “部分树度量”，我们将有限的跳限制问题转化为在树上的无限制跳问题，并且给了许多经典网络设计问题的第一个多对数双标准逼近。这些问题包括斯特纳森林、组斯特纳树、组斯特纳森林、大宗购买网络设计以及在线和迭代多个问题。

Nov, 2020

分支网络中的启发式最优传输

网络中最优传输的分支启发式方法及其应用

Nov, 2023

在图中学习剪枝斯坦纳树问题的实例

本文使用基于机器学习的学习剪枝框架来解决史泰纳树问题，结果显示该框架可在商业整数线性规划求解器所需时间的一小部分时间内计算出近乎最优的解决方案，进一步证明了学习剪枝框架在解决各种组合优化问题方面的潜力。

Aug, 2022

基于最小尺寸约束的聚类间准则优化

我们提出了能够最大化两个自然的距离度量准则（最小间距和最小生成树间距）的算法，并且对无限制情况和有约束情况均给出了结果。我们的方法在实际应用中表现非常好，并通过 10 个真实数据集的经验研究提供了证据。

Jan, 2024

计算 MCMC 搜索系统发生树空间的探索

通过使用适合该任务的子树钳剪与再接（SPR）度量标准，研究了贝叶斯系统发育后分布中的拓扑峰值，并提出了一种基于图形的方法，评价了 MCMC 下的树拓扑结构，并发现在实际数据集中，存在拓扑峰值和连续多峰问题。

May, 2014

通用和可扩展的最优稀疏决策树

通过提出一种决策树优化框架，解决了当前领域中两个开放性问题：不平衡数据处理和连续变量完全优化。此外，我们还介绍了一种可扩展的算法，可以在存在连续变量的情况下产生可证明的最优结果，并相对于现有技术将决策树构建速度提高了数个数量级。

Jun, 2020

跨度树分布下期望值的高效计算

提出了一种用于跨度树模型推断的普适框架，该框架的算法包括第一和第二领域期望。这些算法易于使用，并且利用梯度与期望之间的基本关系，可以有效地计算多种量值，包括期望附加分数，熵和广义期望准则等。

Aug, 2020

扰动生成树的可微聚类

提出了一种基于最小权重生成树的可微聚类方法，通过线性规划的随机扰动实现平滑和高效的梯度计算，从而在端对端可训练流水线中进行聚类，并演示其在高噪声和具有挑战性的数据集上的性能和用于半监督任务的。

May, 2023

最短路径与最小斯坦纳树间的查询决策回归

对于一个具有未知权重的图，如果我们知道一些节点子集关联的最小 Steiner 树，那么我们能否找到一对节点的最短路径？本文研究了这样一个原型问题，称为具有任务转换的查询 - 决策回归，重点关注最短路径问题和最小 Steiner 树问题。我们提供了关于构建评分模型的可实现假设空间设计的理论洞察，并提出了两个有原则的学习框架。我们的实验研究显示，这样的问题可以在统计显著性的程度上得到较好的解决。

Feb, 2024