The defining characteristic of fixed interval scheduling problems is that each job has a finite
number of fixed processing intervals. A job can be processed only in one of its intervals on …

We define a new measure for the quality of online algorithms, the relative worst order ratio,
using ideas from the max/max ratio [Ben-David and Borodin 1994] and from the random …

The relative worst-order ratio, a relatively new measure for the quality of on-line algorithms,
is extended and applied to the paging problem. We obtain results significantly different from …

A new measure, the accommodating function, for the quality of on-line algorithms is
presented. The accommodating function, which is a generalization of both the competitive …

This paper is devoted to the online dominating set problem and its variants. We believe the
paper represents the first systematic study of the effect of two limitations of online algorithms …

The standard measure for the quality of online algorithms is the competitive ratio. This
measure is generally applicable, and for some problems it works well, but for others it fails to …

This paper introduces a novel optimisation problem motivated by the real-world application
of transferring between trains. The driving idea is to minimise the walking distances of all …

We consider a real-time version of the inventory problem with deterministic demand in which
decisions as to when to replenish and how much to buy must be made in an online fashion …

Abstract. We consider the on-line Dual Bin Packing problem where we have n unit size bins
and a sequence of items. The goal is to maximize the number of items that are packed in the …

In this thesis we introduce and evaluate several new models for the analysis of online
algorithms. In an online problem, the algorithm does not know the entire input from the …