A Collection of Lower Bounds for Online Matching on the Line
A Collection of Lower Bounds for Online Matching on the Line
复制标题
线上匹配下界集合
DOI：
10.1007/978-3-319-77404-6_5
复制
发表时间：
2017
期刊：
影响因子：
1.1
通讯作者：
Andreas Tönnis
中科院分区：
文献类型：
--
作者：
A. Antoniadis;Carsten Fischer;Andreas Tönnis
在在线匹配问题中，任务是将一组请求$R$在线匹配到给定的一组服务器$S$。$R\，\cup\，S$中任意两点之间的距离度量是一个线性度量，在线算法的目标是最小化匹配的服务器-请求对之间的距离之和。这个问题已经得到了很好的研究，尽管最近有了改进，但在最知名的下限和上限之间仍然存在很大的差距：这个问题最知名的确定性算法是O（\log^2n）$-竞争性的，而最知名的确定性下限是9.001 $。随机算法的上界和下界分别为$O（\log n）$和$4.5$。
我们证明了任何确定性的在线算法，在每一轮中：$（i）$的基础上的匹配决定只对当前请求的本地信息，和$（ii）$是对称的（在这个意义上，对应于镜像的决定的一些实例$I$是镜像的决定对应于实例$I$），必须是$\Omega（\log n）$-竞争。然后，我们扩展的结果表明，它也持有放松对称性时，使算法可能会更喜欢一边，但只有在一定程度上。这证明了$\Omega（\log n）$对一大类“自然”算法的竞争比的障碍。这门课包括了目前为止在文献中找到的所有确定性的线上演算法。
此外，我们表明，我们的结果可以扩展到随机算法，局部诱导所选服务器的对称分布。竞争比上的$\Omega（\log n）$-障碍也适用于这类算法。
In the online matching on the line problem, the task is to match a set of requests $R$ online to a given set of servers $S$. The distance metric between any two points in $R\,\cup\, S$ is a line metric and the objective for the online algorithm is to minimize the sum of distances between matched server-request pairs. This problem is well-studied and - despite recent improvements - there is still a large gap between the best known lower and upper bounds: The best known deterministic algorithm for the problem is $O(\log^2n)$-competitive, while the best known deterministic lower bound is $9.001$. The lower and upper bounds for randomized algorithms are $4.5$ and $O(\log n)$ respectively.
We prove that any deterministic online algorithm which in each round: $(i)$ bases the matching decision only on information local to the current request, and $(ii)$ is symmetric (in the sense that the decision corresponding to the mirror image of some instance $I$ is the mirror image of the decision corresponding to instance $I$), must be $\Omega(\log n)$-competitive. We then extend the result by showing that it also holds when relaxing the symmetry property so that the algorithm might prefer one side over the other, but only up to some degree. This proves a barrier of $\Omega(\log n)$ on the competitive ratio for a large class of "natural" algorithms. This class includes all deterministic online algorithms found in the literature so far.
Furthermore, we show that our result can be extended to randomized algorithms that locally induce a symmetric distribution over the chosen servers. The $\Omega(\log n)$-barrier on the competitive ratio holds for this class of algorithms as well.