论文标题
在线最低成本匹配与追索权
Online Minimum Cost Matching on the Line with Recourse
论文作者
论文摘要
在线上的最低成本匹配中，$ n $请求一一出现，必须立即与给定的一组服务器进行匹配，全部在真实的线上。目的是最大程度地减少从请求到各自服务器的距离之和。尽管进行了所有研究工作，但是否存在$ O（1）$ - 竞争算法仍然是一个有趣的公开问题。 Raghvendra [SOCG18]最著名的在线算法实现了$θ（\ log n）$的竞争因素。该结果与$ω（\ log n）$ [LATIN18]的下限相匹配，该$ [LATIN18]适用于相当大的在线算法，包括文献中的所有确定性算法。 在这项工作中，我们在求助模型中解决了该问题，在该模型中，我们允许在某种程度上撤销在线决策。我们在最多使用$ o（n \ log n）$重新分配的线路上显示了$ O（1）$ - 竞争性算法。这是与追索权匹配的最小成本二分之一的第一个非平凡结果。对于所谓的交替实例，两个服务器之间的请求不超过一个请求，我们获得了近乎理想的结果。我们给出了$（1+ \ varepsilon）$ - 竞争算法，该算法重新分配了最多$ o（\ varepsilon^{ - 1.001}）$ times的任何请求。这种特殊情况很有趣，因为上述相当一般的下限$ω（\ log n）$在这种情况下保留。
In online minimum cost matching on the line, $n$ requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all on the real line. The goal is to minimize the sum of distances from the requests to their respective servers. Despite all research efforts, it remains an intriguing open question whether there exists an $O(1)$-competitive algorithm. The best known online algorithm by Raghvendra [SoCG18] achieves a competitive factor of $Θ(\log n)$. This result matches a lower bound of $Ω(\log n)$ [Latin18] that holds for a quite large class of online algorithms, including all deterministic algorithms in the literature. In this work we approach the problem in a recourse model where we allow to revoke online decisions to some extent. We show an $O(1)$-competitive algorithm for online matching on the line that uses at most $O(n\log n)$ reassignments. This is the first non-trivial result for min-cost bipartite matching with recourse. For so-called alternating instances, with no more than one request between two servers, we obtain a near-optimal result. We give a $(1+\varepsilon)$-competitive algorithm that reassigns any request at most $O(\varepsilon^{-1.001})$ times. This special case is interesting as the aforementioned quite general lower bound $Ω(\log n)$ holds for such instances.
