Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784

phone: +30 210 7275122
fax: +30 210 7275114

E. Koutsoupias and A. Nanavati. The online matching problem on a line. Workshop on approximation and online algorithms, pages 179--191, Budapest 2003.
Download: pdf ps


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.


@string{WAOA03 = {1st Workshop on Approximation and Online Algorithms}} 

  author =       {E. Koutsoupias and A. Nanavati},
  title =        {The online matching problem on a line},
  booktitle =    WAOA03,
  pages =        {179--191},
  year =         2003,
  address =      {Budapest, Hungary},