In this work an alternative online variant of the matching problem in
bipartite graphs is presented. It is motivated by a scheduling problem
in an online environment. In such an environment, a task is unknown up
to its disclosure. However, in that moment it is not necessary to take
a decision on the service of that particular task. In reality, an
online scheduler has to decide on how to use the current resources.
Therefore, our problem is called `online request server matching'
(ORSM). It differs substantially from the `online bipartite matching'
problem of Karp et al. [KVV90]. Hence, the analysis of an optimal,
deterministic online algorithm for the ORSM problem results in a
smaller competitive ratio of 1.5 .
We also introduce an extension to a weighted bipartite matching
problem. A lower bound of $\frac{\sqrt{5}+1}{2}\approx 1.618$ and an
upper bound of 2 is given for the competitive ratio.
@InProceedings{Riedel/99,
author = {Riedel, Marco},
title = {Online Matching for Scheduling Problems},
booktitle = {Proceedings of the 16th Symposium on Theoretical
Aspects in Computer Science ---STACS~'99, (Trier,
Germany, March 4--6, 1999)},
pages = {571--580},
year = 1999,
editor = {Meinel, Chrisoph and Tison, Sophie},
series = {LNCS 1563},
address = {Berlin-Heidelberg-New York},
publisher = {Springer-Verlag},
}