SIGACT News Online Algorithms Column 28: Online Matching on the Line, Part 2

In the online matching problem on the line, requests (points in R) arrive one by one to be served by a given set of servers. Each server can be used only once. This is a variant of the k-server problem restricted to the real line. Although easy to state, this problem is stil wide open. The best known lower bound is 9.001 [2], showing that this problem is really different from the well-known cow path problem. Antoniadis et al. [1] recently presented a sublinearly competitive algorithm. In this column, I present some results by Elias Koutsoupias and Akash Nanavati on this problem with kind permission of the authors. The column is based on Akash’ PhD thesis [4], which contains an extended version of their joint WAOA 2003 paper [3] which has never appeared in a journal. I have expanded the proofs and slightly reorganized the presentation. The previous column (see SIGACT News 47(1):99-111) contains a proof of a linear upper bound for the generalized work function algorithm and a logarithmic lower bound for the algorithm. This column gives a more detailed analysis of this algorithm, leading to a different (but again linear) upper bound. The techniques used here may potentially be helpful to show a sublinear upper bound for γ-wfa. I conjecture that this algorithm in fact has a logarithmic competitive ratio (which would match the known lower bound for it), but this very much remains an open question.