Edge-weighted Online Stochastic Matching: Beating $1-\frac1e$

基本信息

• 论文ID: 2210.12543
• 标题: Edge-weighted Online Stochastic Matching: Beating $1-\frac1e$
• 作者: Shuyi Yan (哥本哈根大学计算机科学系)
• 分类: cs.DS (数据结构与算法), cs.GT (博弈论)
• 发表时间: 2025年4月8日 (arXiv预印本第3版)
• 论文链接: https://arxiv.org/abs/2210.12543

摘要

本文研究边加权在线随机匹配问题。自从Feldman等人提出$(1-\frac1e)$-竞争性的Suggested Matching算法以来，在一般边加权在线随机匹配问题上一直没有改进。本文首次提出突破$1-\frac1e$屏障的算法，实现了0.645的竞争比。基于Jaillet和Lu提出的线性规划，我们设计了算法预处理，将所有边分为两类。然后基于Suggested Matching算法，调整匹配策略以在早期阶段改善一类边的性能，在后期阶段改善另一类边的性能，同时保持不同边的匹配事件高度独立。通过平衡这些操作，最终保证每条边的匹配概率。

研究背景与动机

问题重要性

在线二部匹配问题自Karp等人在1990年引入以来，在在线算法领域扮演着重要角色。其最重要的应用是在线广告：当用户在搜索引擎上搜索时，需要选择合适的广告展示。在这个问题中，广告商被建模为离线顶点（算法开始时已知），印象（用户搜索）被建模为在线顶点（逐一到达）。

现有方法局限性

1. 最坏情况模型：Karp等人的Ranking算法在无权匹配中达到$1-\frac1e \approx 0.632$的竞争比，并证明了其最优性。
2. 在线随机匹配模型：Feldman等人提出的Suggested Matching算法在一般边加权设置中仍然只能达到$1-\frac1e$的竞争比。
3. 特殊情况的改进：虽然在顶点加权匹配、带自由处置的边加权匹配等特殊情况下已有改进，但一般边加权设置缺乏这些有用性质。

研究动机

一般边加权设置本质上更困难，因为：

• 轻边可能占据离线顶点，阻止重边在未来匹配
• 无法简单地通过下界每个顶点或边的匹配概率来获得好的竞争比
• 上界0.703表明该设置确实比特殊情况更困难

核心贡献

1. 首次突破$1-\frac1e$屏障：在一般边加权在线随机匹配问题中提出竞争比为0.645的多项式时间算法
2. 创新的预处理技术：基于Jaillet-Lu线性规划设计预处理，将边分为两类并简化问题结构
3. 多阶段匹配策略：提出Multistage Suggested Matching算法，在不同阶段采用不同策略优化性能
4. 独立性保持分析：发展了保持不同边匹配事件高度独立的分析框架

方法详解

任务定义

输入：

• 在线顶点类型集合$I$和离线顶点集合$J$
• 边集$E = \{(i,j) : i \in I, j \in J_i\}$，每条边$(i,j)$有非负权重$w_{ij}$
• 每个在线顶点类型$i$的到达率$\lambda_i$

过程：在线顶点按泊松过程到达，每个顶点独立地以概率$\frac{\lambda_i}{\Lambda}$选择类型$i$

目标：最大化所有匹配边的期望总权重

核心技术框架

1. Jaillet-Lu线性规划

使用改进的线性规划界定离线最优解：

maximize ∑_{(i,j)∈E} w_{ij}x_{ij}
subject to:
∑_j x_{ij} ≤ λ_i  ∀i ∈ I
∑_i x_{ij} ≤ 1   ∀j ∈ J  
∑_i (2x_{ij} - λ_i)^+ ≤ 1 - ln 2  ∀j ∈ J
x_{ij} ≥ 0  ∀(i,j) ∈ E

2. 预处理技术

定理2：任何Jaillet-Lu线性规划的解都可以转换为满足以下条件的等价分数匹配：

• $\forall i \in I, x_i = λ_i$ (约束2)
• $\forall j \in J, x_j = 1$ (约束3)
• $\forall (i,j) ∈ E, x_{ij} \in \{0, \frac{1}{2}λ_i, λ_i\}$ (约束4)

这将边分为两类：

• 一类边：$x_{ij} = λ_i$（在线顶点类型只匹配一个离线顶点）
• 二类边：$x_{ij} = \frac{1}{2}λ_i$（在线顶点类型匹配两个离线顶点各一半）

模型架构：Multistage Suggested Matching

算法分为三个时间阶段：

阶段1 ($0 ≤ t ≤ t_0$)：

• 一类顶点：匹配到唯一邻居（如果未匹配）
• 二类顶点：直接丢弃

阶段2 ($t_0 < t ≤ t_1$)：

• 一类顶点：匹配到唯一邻居（如果未匹配）
• 二类顶点：以概率$\frac{1}{2}$匹配到每个未匹配邻居

阶段3 ($t_1 < t ≤ 1$)：

• 一类顶点：匹配到唯一邻居（如果未匹配）
• 二类顶点：
  • 如果在时间$t_1$时只有一个邻居未匹配，则匹配到该邻居
  • 否则以概率$\frac{1}{2}$匹配到每个未匹配邻居

技术创新点

1. 时间分段策略：
   • 早期牺牲二类边来提高一类边的匹配概率
   • 后期观察状态调整二类边策略
2. 独立性维护：
   • 只在时间$t_1$观察一次离线顶点状态
   • 保持不同边匹配事件的高度独立性
3. 概率分析：
   • 独立下界每个离线顶点在任意时间的未匹配概率
   • 基于精确匹配率独立计算每条边的匹配概率

实验设置

本文主要是理论分析，通过数学证明验证算法性能：

参数设置

• 边界时间：$t_0 = 0.05$, $t_1 = 0.757$
• 这些参数通过数值优化获得，进一步调整只能在小数点后第4位改善竞争比

评价指标

竞争比：算法期望目标值与离线最优匹配期望目标值的比值

实验结果

主要结果

定理9：Multistage Suggested Matching算法对边加权在线随机匹配问题是0.645-竞争的。

详细分析

对于一类边$(i,j)$，竞争比为： $\int_0^1 E[A_j(t)]dt ≥ \int_0^{t_0} e^{-y_j t}dt + \int_{t_0}^{t_1} e^{-y_j t_0-(t-t_0)}dt + \int_{t_1}^1 e^{-y_j t_0-(t_1-t_0)-(2-y_j)(t-t_1)}dt$

对于二类边$(i,j)$，竞争比为： $\int_{t_0}^{t_1} E[A_j(t)]dt + E[A_{j'}(t_1)]\int_{t_1}^1 E[A_j(t)|A_{j'}(t_1)=1]dt + 2(1-E[A_{j'}(t_1)])\int_{t_1}^1 E[A_j(t)|A_{j'}(t_1)=0]dt$

关键发现

1. 最坏情况：当$y_j = 1 - \ln 2$时，两类边的竞争比都达到最小值0.645
2. 平衡设计：通过调整$t_0$和$t_1$，算法在每条边上都超过$1-\frac{1}{e} ≈ 0.632$的竞争比
3. 理论保证：严格的数学证明确保了算法的性能下界

相关工作

发展历程

1. 最坏情况模型：
   • Karp等人(1990)：Ranking算法，$1-\frac{1}{e}$竞争比
   • Aggarwal等人：顶点加权扩展
2. 随机顺序模型：
   • Goel和Mehta：Greedy算法，$1-\frac{1}{e}$竞争比
   • Mahdian和Yan：改进到0.696
3. 在线随机匹配：
   • Feldman等人(2009)：首次突破$1-\frac{1}{e}$（无权，整数假设）
   • 顶点加权：0.716竞争比
   • 带自由处置边加权：0.706竞争比
   • 整数假设下边加权：0.705竞争比

本文定位

本文是首个在一般边加权设置下突破$1-\frac{1}{e}$屏障的工作，填补了该领域的重要空白。

结论与讨论

主要结论

1. 理论突破：首次在一般边加权在线随机匹配中实现超过$1-\frac{1}{e}$的竞争比
2. 方法创新：多阶段策略和独立性分析为该领域提供了新的技术工具
3. 性能提升：从0.632提升到0.645，虽然看似微小但在理论上具有重要意义

局限性

1. 改进幅度：相比特殊情况（如顶点加权的0.716），改进幅度相对较小
2. 复杂性：算法需要精确的时间控制和状态观察
3. 理论上界：距离0.703的理论上界仍有差距

未来方向

1. 进一步改进：寻找更好的时间分段策略或匹配规则
2. 实际应用：将理论算法应用到实际在线广告等场景
3. 扩展模型：考虑更一般的到达模式或约束条件

深度评价

优点

1. 重要理论突破：解决了该领域十多年来的开放问题
2. 技术创新性：
   • 巧妙的预处理技术简化问题结构
   • 多阶段策略平衡不同类型边的性能
   • 独立性分析框架具有普适性
3. 数学严谨性：
   • 完整的理论分析和证明
   • 精确的概率计算和界限分析
   • 详细的参数优化过程
4. 问题定位准确：清晰识别一般边加权设置的困难所在

不足

1. 实用性限制：
   • 需要精确的泊松到达假设
   • 时间参数需要精确控制
   • 缺乏实际数据验证
2. 改进幅度：虽然理论上重要，但数值改进相对较小
3. 复杂性：算法设计和分析都相当复杂，实现难度较高

影响力

1. 理论贡献：为在线算法和匹配理论提供了重要进展
2. 方法论价值：多阶段分析和独立性维护技术可能适用于其他问题
3. 启发意义：为进一步改进提供了新的思路和工具

适用场景

1. 在线广告：搜索引擎广告分配
2. 资源分配：云计算资源动态分配
3. 匹配市场：各种在线匹配平台

参考文献

论文引用了该领域的重要工作，包括：

• Karp等人的开创性工作
• Feldman等人的在线随机匹配模型
• Jaillet和Lu的线性规划改进
• 各种特殊情况下的算法改进

总结：这是一篇在理论计算机科学领域具有重要意义的论文，虽然改进幅度看似微小，但解决了该领域的一个重要开放问题，展示了深刻的技术洞察和严谨的数学分析。