Matching, capturing allocation of items to unit-demand buyers, or tasks to workers, or pairs of
collaborators, is a central problem in economics. Indeed, the growing prevalence of …

The classical analysis of online algorithms, due to its worst-case nature, can be quite
pessimistic when the input instance at hand is far from worst-case. Often this is not an issue …

In 1979, Weitzman introduced Pandora's box problem as a framework for sequential search
with costly inspections. Recently, there has been a surge of interest in Pandora's box …

We provide prophet inequality algorithms for online weighted matching in general (non-
bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex …

Prophet inequalities are a useful tool for designing online allocation procedures and
comparing their performance to the optimal offline allocation. In the basic setting of k-unit …

The rich literature on online Bayesian selection problems has long focused on so-called
prophet inequalities, which compare the gain of an online algorithm to that of a" prophet" …

In the classical prophet inequality, a gambler faces a sequence of items, whose values are
drawn independently from known distributions. Upon the arrival of each item, its value is …

This paper leverages machine-learned predictions to design competitive algorithms for
online conversion problems with the goal of improving the competitive ratio when …

We extend the standard online worst-case model to accommodate past experience which is
available to the online player in many practical scenarios. We do this by revealing a random …

In this paper, we study max-weight stochastic matchings on online bipartite graphs under
both vertex and edge arrivals. We focus on designing polynomial time approximation …