Feb, 2024

一个针对最大 $s$- 束问题的带有新界限方法的有效分支限界算法

PDF
TL;DR提出了一种新的基于图分割技术的上界方法（PUB），用于最大 s - 束问题（MBP）的精确算法中，同时使用初始下界和上界对图进行预处理和分支剪枝。通过与其他 BnB MBP 算法的实验证明了该算法的显著进展。
发现论文，激发创造
  • 基于学习的分支定界算法求解最大公共子图问题

    本文提出了一种受强化学习启发式的分枝策略，旨在尽早到达树叶以大大减小搜索树的大小，对于解决典型的最大公共子图（MCS）问题的分枝限界算法具有显著的效果优势。

    May, 2019

  • 基于连通图的成本转移方案

    本文提出了利用 minibucket elimination 和 message-passing updates 两种方法来划定图形模型中 MPE 查询边界的多种算法，采用混合式方法平衡两者优势，实验证明其在 PASCAL2 推理挑战中取得第一名。

    Oct, 2012

  • 用新的价值函数进行混合学习解决最大公共子图问题

    本研究提出了一种新的基于深度强化学习的顶点选择方法与价值函数，应用于求解最大诱导公共子图问题的分支定界算法，并实验验证了新算法的效果明显优于目前最先进的算法 McSplit+LL 和 McSplit+RL，同时分析证明了新的选择方法和价值函数的有效性。

    Aug, 2022

  • 一个基于 SDP 的分支定界算法用于双聚类

    我们提出了一种定制的分支限界算法来解决 $k$-densest-disjoint biclique 问题，通过同时聚类数据矩阵的行和列，找到给定加权完全二分图的 $k$ 个不相交的完全二分子图（称为 bicliques），使它们的密度之和最大化。

    Mar, 2024

  • 基于双分图随机块模型的改进聚类算法

    该研究提出了一种基于谱聚类算法的新方法，可在 Bipartite 随机块模型中使用多项式时间算法实现精确和几乎全面的节点分区恢复，并改进了条件以使用现有算法进行近乎完全恢复，以及使用种植可满足问题与 BSBM（Bipartite 随机块模型）之间的联系进行研究以完全恢复种植任务。

    Nov, 2019

  • 最大团问题的搜索树形状及其对并行分支界限的影响

    通过比较两种基于多核线程并行的最大团问题的分支定界算法的并行适应性，进一步提出了一种低开销、可扩展的工作分割机制，并通过解释并行搜索顺序和搜索空间内解的可能位置之间的交互来说明成功的原因。

    Jan, 2014

  • 半定规划层次结构在图模型推断中的应用

    本文提出使用具有两个创新的二进制 SDP 松弛，同时聚焦于计算效率的 SOS 层次结构进行 MAP 推理，该算法在实际问题如图像去噪和 Ising 自旋玻璃方面表现优于 BP 和 GBP。

    Sep, 2017

  • 快速、可扩展、带有谱绑定和素描的半定规划温启动

    用于解决大规模 SDP 问题的 SpecBM 算法具有渐近最优的收敛速度和快速计算时间，在多个应用中展现了其在大规模实例上的实证效果。

    Dec, 2023

  • 关于最大二分匹配的两遍流算法

    该研究研究了二遍流算法在最大二分匹配上的应用，提出了结合子抽样和贪心匹配算法以及度有界半匹配算法的元算法，证明了近似算法的下限，并且发现了最优算法，同时也强调了需求使用新技术以进一步改进。

    Jul, 2021

  • 有限查询图连接性测试

    提出了一种组合优化模型，可以在限定次数的查询下寻找图中两点的连通性，创新性地提出了一种较为可扩展的精确算法以及适用于大规模数据的启发式算法。

    Feb, 2023