在本文中，我们研究了在线最小成本完美匹配延迟 (MPMD) 问题，其中有 $m$ 个请求在 $n$ 个点的度量空间中到达。在 MPMD 中，算法可以选择匹配请求或延迟，目标是最小化连接和延迟成本的总和。匹配的连接成本是两个匹配请求在度量空间中的距离，而延迟成本的增加则是未匹配请求集合的函数。
我们研究了两种不同类型的延迟函数：基于大小的 (MPMD-Size) 和凸延迟 (MPMD-Convex)。MPMD-Size 的研究由 Deryckere 和 Umboh 在 2023 年的 APPROX/RANDOM 会议上开始，其中瞬时延迟增量是未匹配请求数量的非负单调函数。我们的界限是以 $n$ 为基础，而 Deryckere 和 Umboh 的界限依赖于 $m$。我们的结果解决了确定性竞争比（最高到常数）。
这些结果的核心是将给定 $n$ 点度量上的 MPMD-Size 简洁编码为 $2^{n-1}$ 点度量上的任务系统问题。我们还考虑了 Liu 等人提出的 MPMD-Convex，其中每个请求的延迟成本是其到达时间与算法匹配时刻之间时间差的统一凸延迟函数。他们关注的延迟函数 $f$ 是无界的、非递减的、连续的，并满足 $f(0)=f'(0)=0$，并表明对于 $n$ 点统一度量，确定性竞争比为 $\Omega(n)$。
令人惊讶的是，当 $f$ 是一个非负的单调多项式且 $f'(0) > 0$ 时，对于统一度量存在一个 $O(1)$ 竞争的确定性算法。我们的结果完成了对统一度量上 MPMD-Convex 的广泛函数类别的理解。
博主点评： 本文展示了在线匹配问题中的延迟成本处理的深入研究，特别是在基于大小与凸函数的场景下。通过清晰的理论界限和算法的构建，为相关领域的研究提供了重要的参考和启示，值得关注。