Online request server matching

AbstractIn the following paper an alternative online variant of the matching problem 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 revealed, it is not necessary to take a decision on the service of that particular task. On the contrary, an online scheduler has to decide on how to use the current resources. Therefore, the problem is called online request server matching (ORSM). It differs substantially from the online bipartite matching problem of Karp et al. (Proc. 22nd Annual ACM Symp. on Theory of Computing, Baltimore, Maryland, May 14–16, 1990, ACM Press, New York, 1990). Hence, the analysis of an optimal, deterministic online algorithm for the ORSM 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 modifications are realized by restrictions on the input structure. Decreased competitive ratios are presented for some of these modified models