The Power of Greedy for Online Minimum Cost Matching on the Line
The Power of Greedy for Online Minimum Cost Matching on the Line
复制标题
DOI：
10.1145/3580507.3597794
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Eric Balkanski;Yuri Faenza;Noémie Périvier
中科院分区：
文献类型：
--
作者：
Eric Balkanski;Yuri Faenza;Noémie Périvier
在在线最小成本匹配问题中，有n个服务器，并且在n个时间步中的每一个时间步，请求到达并且必须可替换地匹配到尚未匹配的服务器，目标是最小化匹配对之间的距离之和。在线最低成本匹配是打车平台和食品配送服务等应用的核心问题。尽管在最坏的情况下，即使在线路上，竞争比也是n的指数，但简单的贪婪算法将每个请求与其最近的可用服务器相匹配，在实践中表现良好，并且具有许多有吸引力的功能，例如防策略性。因此，一个主要的问题是如何解释贪婪的强大的经验表现。在本文中，我们的目标是了解贪婪的性能在至少部分随机的情况下。当请求和服务器都是从[0，1]中均匀且独立地绘制时，我们获得了贪婪的恒定竞争比，这在此设置中改进了贪婪的[EQUATION]之前最知名的界限。我们还表明，这种恒定的竞争比也持有过剩供应设置，其中有一个线性过剩的服务器，这提高了以前最有名的边界O（log3 n）贪婪在此设置。此外，我们表明，在半随机模型中的请求仍然是统一和独立的，但在服务器的选择adversarially，贪婪实现了O（log n）的竞争比。即使这种单边随机性允许贪婪的竞争比的大幅度提高相比，该模型中的请求是完全对抗性的或以随机顺序到达，我们表明，它是不够的，以获得一个恒定的竞争比给出一个严格的Ω（log n）的下限。这些结果邀请进一步调查有多少随机性是必要的和足够的，以获得强有力的理论保证贪婪算法在线最小成本匹配，在线和超越。这篇论文的完整版本可以在https://arxiv.org/abs/2210.03166上找到。
In the online minimum cost matching problem, 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, with the goal of minimizing the sum of the distances between the matched pairs. Online minimum cost matching is a central problem in applications such as ride-hailing platforms and food delivery services. Despite achieving a worst-case competitive ratio that is exponential in n even on the line, the simple greedy algorithm, which matches each request to its nearest available server, performs well in practice and has a number of attractive features such as strategyproofness. A major question is thus to explain greedy's strong empirical performance. In this paper, we aim to understand the performance of greedy on the line over instances that are at least partially random. When both the requests and the servers are drawn uniformly and independently from [0, 1], we obtain a constant competitive ratio for greedy, which improves over the previously best-known bound of [EQUATION] for greedy in this setting. We also show that this constant competitive ratio also holds in the excess supply setting where there is a linear excess of servers, which improves over the previously best-known bound of O(log3 n) for greedy in this setting. 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. Even though this one-sided randomness allows a large improvement in greedy's competitive ratio compared to the model where the requests are fully adversarial or 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. A full version of this paper can be found at https://arxiv.org/abs/2210.03166.