May, 2009

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

PDF
TL;DR本研究介绍了一种算法来解决在线随机二分匹配问题，提供了一个 0.67 的逼近比和一种基于流量图和最大流问题的新方法来解决这个问题。
发现论文，激发创造
  • 在线顶点加权二分匹配：通过随机到达击败 1-1/e

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

    Apr, 2018

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

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

    Jun, 2016

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

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

    May, 2015

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

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

    May, 2024

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

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

    Jul, 2010

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

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

    Jul, 2010

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

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

    Mar, 2021

  • 资源分配问题的近最优在线算法和快速近似算法

    本文提出一种针对多个资源分配问题的算法体系，将在线请求建模为每次从未知的概率分布中独立抽取，给出了一个在任意接受数据的情况下获得一定比例最优解的单一算法，并且探究了如何在任意情况下应对敌对分布。同时，文中提出了解决大型 LPs 混合装填覆盖问题的快速算法，并分析了该算法在在线拍卖、网络路由和广告策略方案等特殊情况下的应用。

    Mar, 2019

  • 当 LP 成为解决你的匹配烦恼的良方：随机匹配的改进界限

    本研究研究了一种随机图模型和匹配问题，提出了基于线性规划和贪心的近似算法，并探讨了匹配问题在肾脏交流和在线广告上的应用。

    Aug, 2010

  • 无知几乎是福利：少数查询下几近最优的随机匹配

    本文提出应用于随机匹配问题和随机集合覆盖问题的边缘和集合查询算法，分别基于自适应和非自适应策略，并将结果扩展到肾脏交换问题等实际问题上，结果表明即使在每个顶点上进行非常少量的非自适应边缘查询，也可以大大提高成功匹配率。

    Jul, 2014