Online request server matching

In the following paper an alternative online variant of the matching proble m in bipartite graphs is presented, It is triggered by a scheduling problem . There, a task is unknown up to its disclosure. However, when a task is re vealed, it is not necessary to take a decision on the service of that parti cular task. On the contrary, an online scheduler has to decide on how to us e the current resources. Therefore, the problem is called online request se rver matching (ORSM). It differs substantially from the online bipartite ma tching problem of Karp et al. (Proc. 22nd Annual ACM Symp. on Theory of Com puting, Baltimore, Maryland, May 14-16, 1990, ACM Press, New York, 1990). H ence, the analysis of an optimal, deterministic online algorithm for the OR SM problem results in a smaller competitive ratio of 1.5. An extension to a weighted bipartite matching problem is also introduced, and results of its investigation are presented. Additional concepts for the ORSM model (e.g. lookahead, parallel resources, deadlines) are studied. All of these modific ations are realized by restrictions on the input structure. Decreased compe titive ratios are presented for some of these modified models. (C) 2001 Els evier Science B.V. All rights reserved.