论文标题
与凹入延迟问题的最小成本匹配
The Min-Cost Matching with Concave Delays Problem
论文作者
论文摘要
我们考虑在线最小成本完美匹配与凹形延迟的问题。我们从单个位置变体开始。具体来说，请求以在线方式到达一个位置。然后，算法必须在匹配一对请求或延迟以后匹配的算法之间进行选择。成本由延迟上的凹功能定义。给定的线性甚至凸延迟功能，匹配任意两个可用请求都是最佳的。但是，这不会扩展到凹形延迟。我们通过提供通过一系列延迟计数器来定义的$ O（1）$ - 竞争算法来解决此问题。 此后，我们考虑了鉴于基本$ n $ points度量的问题。然后将匹配的成本定义为连接成本（由度量标准定义）加上延迟成本。给定线性延迟，Emek等人引入了此问题。并以线性延迟（MPMD）问题称为最小成本的完美匹配。刘等。考虑到凸的延迟，随后询问是否存在具有较小竞争比的解决方案给定凹形延迟。我们通过扩展单个位置算法并证明$ O（\ log n）$竞争力来证明这是正确的。最后，我们将重点转移到了双重情况下，其中请求具有极性，并且只能匹配相反的极性。我们展示了如何更改以前的算法，以再次实现单个位置和公制案例的$ O（1）$和$ O（\ log n）$竞争力。
We consider the problem of online min-cost perfect matching with concave delays. We begin with the single location variant. Specifically, requests arrive in an online fashion at a single location. The algorithm must then choose between matching a pair of requests or delaying them to be matched later on. The cost is defined by a concave function on the delay. Given linear or even convex delay functions, matching any two available requests is trivially optimal. However, this does not extend to concave delays. We solve this by providing an $O(1)$-competitive algorithm that is defined through a series of delay counters. Thereafter we consider the problem given an underlying $n$-points metric. The cost of a matching is then defined as the connection cost (as defined by the metric) plus the delay cost. Given linear delays, this problem was introduced by Emek et al. and dubbed the Min-cost perfect matching with linear delays (MPMD) problem. Liu et al. considered convex delays and subsequently asked whether there exists a solution with small competitive ratio given concave delays. We show this to be true by extending our single location algorithm and proving $O(\log n)$ competitiveness. Finally, we turn our focus to the bichromatic case, wherein requests have polarities and only opposite polarities may be matched. We show how to alter our former algorithms to again achieve $O(1)$ and $O(\log n)$ competitiveness for the single location and for the metric case.
