论文标题
贪婪在线最低成本匹配的力量
The Power of Greedy for Online Minimum Cost Matching on the Line
论文作者
论文摘要
我们考虑在线上有$ n $服务器的在线最低成本匹配问题，并且在$ n $ time步骤中的每一个中，请求到达，并且必须不可撤销地与尚未与之匹配的服务器匹配，目的是最大程度地减少匹配对之间的距离之和。尽管达到了最差的竞争比率，但在$ n $中的指数级，但简单的贪婪算法将每个请求与其最近的免费服务器匹配，但在实践中表现良好。因此，一个主要的问题是解释贪婪的强烈经验表现。在本文中，我们旨在了解至少部分随机的实例贪婪的表现。当请求和服务器都均匀绘制并独立于$ [0,1] $绘制时，我们表明贪婪是持续的竞争力，它比以前最著名的$ o（\ sqrt {n}）$改善。我们将这个恒定的竞争比率扩展到具有线性超过服务器的设置，该设置比以前最著名的$ o（\ log^3 {n}）$绑定了。我们还表明，在半随机模型中，请求仍然均匀，独立地绘制，但在对手选择服务器的情况下，贪婪可以实现$ O（\ log {n}）$竞争比率。当请求以随机订单而到达但在对抗中选择时，以前知道贪婪为$ O（n）$ - 竞争力。即使这种单方面的随机性可以与请求是对抗性并以随机顺序到达的模型相比，贪婪的竞争比有很大的改善，但我们表明，通过给出紧密的$ω（\ log {n}），获得恒定的竞争比不足以获得恒定的竞争比。这些结果邀请进一步研究需要多少随机性，足以获得贪婪算法的强大理论保证，以在线及以后的在线最低成本匹配。
We consider the online minimum cost matching problem on the line, in which there are $n$ servers and, at each of $n$ time steps, a request arrives and must be irrevocably matched to a server that has not yet been matched to, with the goal of minimizing the sum of the distances between the matched pairs. Despite achieving a worst-case competitive ratio that is exponential in $n$, the simple greedy algorithm, which matches each request to its nearest available free server, performs very well in practice. A major question is thus to explain greedy's strong empirical performance. In this paper, we aim to understand the performance of greedy over instances that are at least partially random. When both the requests and the servers are drawn uniformly and independently from $[0,1]$, we show that greedy is constant competitive, which improves over the previously best-known $O(\sqrt{n})$ bound. We extend this constant competitive ratio to a setting with a linear excess of servers, which improves over the previously best-known $O(\log^3{n})$ bound. We moreover show that in the semi-random model where the requests are still drawn uniformly and independently but where the servers are chosen adversarially, greedy achieves an $O(\log{n})$ competitive ratio. When the requests arrive in a random order but are chosen adversarially, it was previously known that greedy is $O(n)$-competitive. Even though this one-sided randomness allows a large improvement in greedy's competitive ratio compared to the model where requests are adversarial and arrive in a random order, we show that it is not sufficient to obtain a constant competitive ratio by giving a tight $Ω(\log{n})$ lower bound. These results invite further investigation about how much randomness is necessary and sufficient to obtain strong theoretical guarantees for the greedy algorithm for online minimum cost matching, on the line and beyond.
