文件名称：批处理和最优多阶段二分分配-研究论文
文件大小：797KB
文件格式：PDF
更新时间：2024-06-29 11:45:24
Online algorithms Matching
在在线市场*需实时匹配的多个应用中，该平台可以允许一些延迟来批量需求并提高匹配效率。 受这些场景的启发，我们研究了在线分配中批处理和低效率之间的最佳权衡。 特别是，我们考虑了经典顶点加权二分 b 匹配和 AdWords 问题的 K 阶段变体，其中在线顶点以 K 批次的形式到达。 我们对这两个问题的主要结果是一个最优的 (1-(1-1/K)^K)-竞争（分数）匹配算法，提高了以这些问题的在线变体而闻名的经典（1-1/e）竞争比率（Mehta 等人，2007 年；Aggarwal 等人，2011 年）。 我们的主要技术是使用一系列基于凸规划的匹配，以特别平衡的方式在不同阶段的供应之间分配需求。 更准确地说，我们确定了一系列“度数递减的多项式”，它们可以用作最优匹配线性程序的严格凹正则化器，以形成这个族。 通过使用这些凸程序的最优解提供底层图的结构分解，我们开发了一个新的多阶段原始对偶框架来分析分数多阶段算法，该算法在每个阶段返回相应的正则化最优匹配（通过求解阶段的凸程序）。 我们通过提供问题的未加权实例进一步显示匹配的上限，其中没有在线算法获得比 (1-(1-1/K)^K) 更好的竞争比率。 我们将结果扩展到大预算的顶点加权 b 匹配问题中的积分分配，以及小预算出价比的 AdWords 问题中的积分分配。