In this report we study a new variant of an online bipartite matching
problem, which can be interpreted as a scheduling problem. Then, we have
one resource, called 'server', which is available for one unit in every
step of a discrete time model. At most one task with unit demand can
occur per time step. It is called 'request', and specifies a set of time
steps when the serving is accepted. These times must not be situated in
the past and neither need to be consecutive nor include the time of the
arrival of the request. After the arrival of a request in time step $i$,
an online algorithm has to decide which request will be served in step
$i$. This decision has to be made without knowledge of future requests.
The objective is a maximization of the number of served requests.
It is obvious, how to model this scheduling problem with a matching
problem in a bipartite graph. However, this online bipartite matching
problem differs considerably from the model in [Karp/Vazirani/Vazirani
'90]. So we call our model 'online request server matching' (ORSM).
Indeed, it is a special case of the 'roommates problem', that was
introduced in [Bernstein/Rajagopalan '93].
To investigate the ORSM problem, we use competitive analysis. A lower
bound of the competitive ratio of 1.5 is shown, and an optimal
1.5-competitive online algorithm is presented. Additionally, a weighted
variant of the ORSM problem (wORSM) is investigated. Here, every edge
has a weight and the objective is the online construction of a matching
with maximal overall weight. For the wORSM problem a general lower bound
of 1.618 for the competitive ratio is shown. A presented online
algorithm is proven to be 2-competitive.
@TechReport{Riedel/98,
author = {Riedel, Marco},
title = {Online Request Server Matching},
institution = {University of Paderborn, Germany},
year = 1998,
month = apr,
number = {tr-ri-98-195}
}