ICMLMay, 2024

在线带有有限指导的二部图匹配

PDF
TL;DR研究在线非加权二分图匹配中的问题，其中有 n 个离线顶点和 n 个在线顶点，并且希望与最佳离线算法保持竞争力。尽管 Karp 等人 [1990] 的经典 RANKING 算法可以证明达到 1-1/e>1/2 的竞争比率，但我们表明在对抗性到达模型中，没有学习增强方法既可以是 1 - 一致的又可以比 1/2 - 健壮。同时，在随机到达模型下，我们展示了如何利用分布测试方法设计出一种算法，该算法接受关于在线顶点的外部建议，并在竞争比率上从不需要建议的方法和最优比率 1 之间插值，这取决于建议的质量。
online unweighted bipartite matchingcompetitive ratiooffline algorithmlearning-augmented methodadversarial arrival model
发现论文，激发创造
  • 在线顶点加权二分匹配：通过随机到达击败 1-1/e

    介绍一种加权排名算法，对于在线顶点以随机顺序到达时的顶点加权二分匹配问题证明了 0.6534 的竞争比率。基于 Devanur 等人的随机原始对偶框架，设计了一个二维收益共享函数来提高算法的竞争比率，并在在线二分匹配问题中达到了大于 1-1 /e 的拓展比率。

    Apr, 2018

  • 在线随机匹配：超越 1-1/e

    本研究介绍了一种算法来解决在线随机二分匹配问题，提供了一个 0.67 的逼近比和一种基于流量图和最大流问题的新方法来解决这个问题。

    May, 2009

  • 在线随机匹配：新算法和界限

    本文提出了一些基本的算法变体和改进，旨在提高已知 IID 模型和具有随机奖励延伸的模型的竞争比率，另外提出了加强型线性规划基准来提高非加权边的概率的情况。

    Jun, 2016

  • 在线随机匹配，泊松到达和自然线性规划

    研究在线随机匹配问题，提出了基于 Poisson 到达模型的 0.711 竞争性算法和近似等价性证明，应用线性规划和 Jensen 不等式实现算法优化，推出第一个在较弱随机到达模型下的节点加权在线随机匹配算法。

    Mar, 2021

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

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

    Jul, 2010

  • 半在线二分匹配

    本文介绍了半在线模型，分析了其应用于二分图匹配问题的效果，给出了竞争性的算法并证明其同样具有竞争性，竞争度可以在完全在线模型和完全离线模型之间插值。

    Dec, 2018

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

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

    May, 2015

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

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

    May, 2023

  • 在线随机匹配：基于离线统计的在线行为

    本论文提出一种基于 Monte Carlo 采样的在线算法，在解决传播广告分配问题的同时，实现 competing ratio 为 0.702，也证明了当到达速率为整数时 competing ratio 为 0.705。同时，我们还证明采用已知分布模型无法实现 competing ratio 小于 0.823。

    Jul, 2010

  • 在线计算与不可信的建议

    该研究考虑了在线计算的建议模型下，建议来源于不受信任的源头所带来的影响，并以滑雪租赁、装箱问题等在线问题为研究对象，得出了根据建议是否可信获得最差情况下的竞争性质算法的结论，解决了现有模型无法解决的差异化问题。

    May, 2019