The Power of Greedy for Online Minimum Cost Matching on the Line

Eric Balkanski, Yuri Faenza, Noemie Perivier

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 t…