KDDFeb, 2024

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

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

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

    Aug, 2022

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

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

    Jun, 2024

  • GAT-Steiner: 使用 GNN 进行直角斯坦纳最小树预测

    研究论文提出了 GAT-Steiner，一种基于图注意力网络模型，能够高准确率地预测 ISPD19 基准测试中 99.846% 的网段，并在次优网长中仅产生 0.480% 的平均增加。在随机生成的基准测试中，GAT-Steiner 在 99.942% 的网段中高准确率地预测，并且在次优网长中仅产生 0.420% 的平均增加。

    Jul, 2024

  • 在线部分监督下的最短路径问题

    研究了在线最短路径问题及其各种监控模型，在加权有向无环图中寻找一条路径以使其对应的边权和尽可能小。提出了一种算法，将累积损失最小化，并介绍了其应用于包交换网络中路由的模拟结果。

    Apr, 2007

  • 最紧代理可接受最短路径

    在加权有向图中解决最短路径问题时，考虑边权重计算时间以及与权重不确定性的关系可以提高性能。通过建立在加权有向图的通用框架上，引入了找到最紧适应最短路径（TASP）的问题，该路径在最优成本的上界上最紧缩，实现了对有界不确定性的最短路径问题的泛化，其中可以用计算成本代替边权重的不确定性。我们提出了一个完整的算法来解决 TASP，并对解决方案的质量进行了保证。实证评估支持这种方法的有效性。

    Aug, 2023

  • 具有多个边成本估计的图的最短路径问题的推广

    本文提供了一种面向带权有向图的广义框架，可以计算（估算）多次边权重，并以不同准确性和运行时开销进行优化，从而提出了一个最短路径问题的广义形式。我们介绍了该问题的一个完整的任何时刻的解法算法，并在实验中证明了其有效性。

    Aug, 2022

  • 在线斯坦纳树学习增强算法

    本文考虑了将机器学习与在线算法设计相结合的新型 “超越最坏情况” 算法分析模型在在线 Steiner 树问题上的应用，其中预测的终端节点可能不正确，算法性能取决于错误预测的数量，可以通过正确预测来突破在线下界并且具有良好的竞争比，同时实验证明该理论具有预测性。

    Dec, 2021

  • 学习带查询的决策树是 NP - 难问题

    证明了使用查询从头系统地学习决策树是 NP 难的，解决了学习理论中悬而未决的一个问题。在证明中，通过引入硬度凝聚的概念，简化并加强了决策树极小化的最优下界，并研究了决策树复杂度的硬度凝聚。结果展示了分布假设在该问题上的戏剧性影响。

    Jul, 2023

  • 随机最短路径问题的变体

    本文介绍了关于随机最短路径问题的算法和策略，提供多种保证路径长度分布，而不仅是期望值最小的解决方案，并对最近在马尔科夫决策过程的研究成果进行了应用。

    Nov, 2014

  • 利用图神经网络协助蒙特卡罗树搜索实现近乎最优斯坦纳树

    本研究介绍了一种通过结合图神经网络和蒙特卡罗树搜索来计算 Steiner 树的方法，该方法在许多不同类型的图上反复优于标准的 2 逼近算法，通常找到最优解。

    Apr, 2023