While methods for optimization under uncertainty have been studied intensely over the past
decades, the explicit consideration of the interplay between uncertainty and time has gained …

The k-server problem is perhaps the most influential online problem: natural, crisp, with a
surprising technical depth that manifests the richness of competitive analysis. The k-server …

Machine-learned predictors, although achieving very good results for inputs resembling
training data, cannot possibly provide perfect predictions in all situations. Still, decision …

Planning algorithms are impacting technical disciplines and industries around the world,
including robotics, computer-aided design, manufacturing, computer graphics, aerospace …

Group testing has been used in medical, chemical and electrical testing, coding, drug
screening, pollution control, multiaccess channel management, and recently in data …

This paper provides a novel technique for the analysis of randomized algorithms for
optimization problems on metric spaces, by relating the randomized performance ratio for …

We study several versions of the shortest-path problem when the map is not known in
advance, but is specified dynamically. We are seeking dynamic decision rules that optimize …

In practice, almost all dynamic systems require decisions to be made on-line, without full
knowledge of their future impact on the system. A general model for the processing of …

The paging problem is that of deciding which pages to keep in a memory of k pages in order
to minimize the number of page faults. We develop the marking algorithm, a randomized on …

Competitive analysis is concerned with comparing the performance of on-line algorithms
with that of optimal off-line algorithms. In some cases randomization can lead to algorithms …