Elias Koutsoupias / Publications

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.

@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},
}