IJCAIMay, 2020

在线广告中大规模最大加权 b 匹配问题的启发式搜索加速学习

PDF
TL;DR提出了 exttt {NeuSearcher} 算法解决大规模、动态的二部匹配问题，该算法基于多通道图神经网络，通过预测匹配边的权重阈值显著减少搜索区域，并结合并行启发式搜索算法迭代提高解决方案的质量，实验证明这种方法能提高 2 至 3 倍的运行速度，同时实现与最先进的近似算法相同的匹配解决方案。
发现论文，激发创造
  • 神经双分图匹配

    本文介绍了如何利用单个图神经网络的特征，通过神经执行将复杂算法（如最大二分匹配）转化为流量问题，并使用 Ford-Fulkerson 算法实现最大流问题的求解，该方法取得了 100% 的理想匹配效果。

    May, 2020

  • 在线二分匹配的深度策略：一种强化学习方法

    本文提出了一个端到端的强化学习框架，基于历史数据的试错，通过设置神经网络架构和设计特征表示，对在线匹配问题进行更好的匹配决策。在两个在线匹配问题中，我们的模型表现得比传统算法更好，提高了匹配质量约 3-10％，代码可在给出的 URL 中公开获得。

    Sep, 2021

  • 多机器人任务分配中带有学习激励函数的大图匹配加权

    该论文介绍了一种使用图强化学习 (GRL) 框架来学习多机器人任务分配 (MRTA) 的启发式或激励的方法，其中使用胶囊注意力策略模型来学习如何赋予任务 / 机器人配对 (边) 在将任务集与机器人集连接的二分图中的权重。该方法与使用专家指定启发式的原始二分图匹配方法性能相当，但具有显著的鲁棒性优势。在训练过程中，学到的激励策略与专家指定的激励策略初始接近，然后稍微偏离其趋势。

    Mar, 2024

  • NP 难问题中启发式近似算法的（不）可扩展性

    本文探讨利用神经网络逼近完全信息启发式函数的可行性，发现对于 NP 难问题，其网络规模可能呈指数级上升，并建议研究方向转向寻找其他机器学习与启发式搜索相结合的方法。

    Sep, 2022

  • 通过学习对偶项快速配对

    通过将机器学习预测和 “热启动” 原始对偶算法的想法相结合，我们考虑了一个最重要的组合优化问题：加权二分匹配及其推广到 b - 匹配，并在真实数据和合成数据上验证了理论发现。

    Jul, 2021

  • 带期限的最大权重在线匹配

    研究匹配到一个时间市场上的代理人的问题，该论文提出了不同的算法来解决顺序不同的场景，并在独立抽样的时间场景中实现 1/8-competitive 算法，对于随机顺序情况下提出了一个每 (d+1) 阶段计算最大加权匹配的 batching 算法，并且证明了其 0.279-competitive 的竞争性。

    Aug, 2018

  • 随机匹配问题的改进近似算法

    本文研究了随机匹配问题，提出一种能够提高精度的探测边的新方法和其在最大化构建匹配的期望收益中的应用，尤其在求解在线偏二分图情况时取得了显著提升。

    May, 2015

  • 在线顶点加权二分匹配和单次出价预算配置

    研究了一种顶点加权的在线二分图匹配算法，使用随机扰动顶点权重的多样化方法，得到了一种最佳 $(1- rac {1} {e})$ 竞争性算法，该算法是现有算法的一般化，为在线资源分配问题提供了新的见解。

    Jul, 2010

  • 具有截止时间实例的快速高效匹配算法

    介绍一种具有截止时间使用市场模型的在线加权匹配问题算法，并使用 FastGreedy 和 FastPostponedGreedy 算法来获得更好的时间复杂度和更高的竞争比。

    May, 2023

  • 具有强鲁棒性保证的边加权在线二分匹配学习

    本研究提出了一种基于强化学习的新型边权重在线二分图匹配方法（LOMAR），以实现良好的平均情况和最坏情况下的性能，其中，关键新颖的操作是根据谨慎的条件决定是否跟随专家的决策还是 RL 决策。

    May, 2023