E. Koutsoupias and A. Nanavati.

**The online matching problem on a line.***Workshop on approximation and online algorithms*, pages 179--191, Budapest 2003.### Abstract

We study the*online matching*problem when the metric space is a single straight line. For this case, the offline matching problem is trivial but the online problem has been open and the best known competitive ratio was the trivial $\Theta(n)$ where $n$ is the number of requests. It was conjectured that the generalized

*Work Function Algorithm*has constant competitive ratio for this problem. We show that it is in fact $\Omega(\log n)$ and $O(n)$, and make some progress towards proving a better upper bound by establishing some structural properties of the solutions. Our technique for the upper bound doesn't use a potential function but it reallocates the online cost in a way that the comparison with the offline cost becomes more direct.

### Bib

@string{WAOA03 = {1st Workshop on Approximation and Online Algorithms}} @InProceedings{KN03b, author = {E. Koutsoupias and A. Nanavati}, title = {The online matching problem on a line}, booktitle = WAOA03, pages = {179--191}, year = 2003, address = {Budapest, Hungary}, }