The Power of Greedy for Online Minimum Cost Matching on the Line
Eric Balkanski, Yuri Faenza, Noémie Périvier · 2023
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.