Apr, 2018

在线顶点加权二分匹配：通过随机到达击败 1-1/e

PDF
TL;DR介绍一种加权排名算法，对于在线顶点以随机顺序到达时的顶点加权二分匹配问题证明了 0.6534 的竞争比率。基于 Devanur 等人的随机原始对偶框架，设计了一个二维收益共享函数来提高算法的竞争比率，并在在线二分匹配问题中达到了大于 1-1 /e 的拓展比率。
发现论文，激发创造
  • 在线顶点加权二分匹配和单次出价预算配置

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

    Jul, 2010

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

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

    May, 2024

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

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

    May, 2009

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

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

    Mar, 2021

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

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

    Jun, 2016

  • 面向带客户偏好的服务在线提前预定调度

    本文研究预约服务的 Web 和移动应用程序，针对该类问题提出了带性能保证的新算法，并在纽约市卫生系统的预约数据上进行了测试。

    May, 2018

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

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

    Aug, 2018

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

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

    May, 2015

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

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

    Jul, 2010

  • 通过子模性在在线二分匹配中平衡相关度和多样性

    本文介绍了在线子模二分图匹配问题（Online Submodular Bipartite Matching）的概念和算法，该问题旨在在考虑到多样性和相关性的情况下，通过优化子模函数 $f$ 来匹配边的集合以得到最佳匹配。

    Nov, 2018