This paper presents a new research direction for the Min-cost Perfect Matching with Delays (MPMD) - a problem introduced by Emek et al. (STOC'16). In the original version of this problem, we are given an $n$-point metric space, where requests arrive in an online fashion. The goal is to minimise the matching cost for an even number of requests. However, contrary to traditional online matching problems, a request does not have to be paired immediately at the time of its arrival. Instead, the decision of whether to match a request can be postponed for time $t$ at a delay cost of $t$. For this reason, the goal of the MPMD is to minimise the overall sum of distance and delay costs. Interestingly, for adversarially generated requests, no online algorithm can achieve a competitive ratio better than $O(\log n/\log \log n)$ (Ashlagi et al., APPROX/RANDOM'17). Here, we consider a stochastic version of the MPMD problem where the input requests follow a Poisson arrival process. For such a problem, we show that the above lower bound can be improved by presenting two deterministic online algorithms, which, in expectation, are constant-competitive. The first one is a simple greedy algorithm that matches any two requests once the sum of their delay costs exceeds their connection cost, i.e., the distance between them. The second algorithm builds on the tools used to analyse the first one in order to obtain even better performance guarantees. This result is rather surprising as the greedy approach for the adversarial model achieves a competitive ratio of $\Omega(m^{\log \frac{3}{2}+\varepsilon})$, where $m$ denotes the number of requests served (Azar et al., TOCS'20). Finally, we prove that it is possible to obtain similar results for the general case when the delay cost follows an arbitrary positive and non-decreasing function, as well as for the MPMD variant with penalties to clear pending requests.
翻译:本文为“ 最低成本完美与延迟匹配” (MPMD) 提供了一个新的研究方向。 这是 Emek 等人(STOC'16) 提出的一个问题。 在这个问题的原始版本中, 我们得到了一个美元点的公用空间, 请求以在线方式到达。 目标是将偶数请求的匹配成本降到最低。 然而, 与传统的在线匹配问题相反, 一项请求在到达时不必立即配对。 相反, 是否匹配请求的决定可以推迟, 美元, 以美元为美元。 因此, MPMD 的目标是将距离和延迟成本的总和降到最低。 有趣的是, 任何在线算法的相对比 $O (\ log n/\ log\ log\ log n) ( Asxlagi et al., APROX/ RANDOM'17) 。 我们在这里考虑的是“ MPMD” 问题的一个随机版本, 其输入请求先以Poisson 美元的运算算。 因此, 我们使用一个更低的算的算法, 当一个简单的算出一个直线上, 一个比一个直方的要求。