Online algorithms have long been studied as a means to handle
uncertainty in optimization. In these problems, the input is slowly revealed
online and the algorithm must maintain a feasible solution with the part of the
input which has been revealed, while at all times having performance comparable
with the optimal offline solution for the partially arrived input. While it has
led to numerous beautiful algorithmic techniques, there are many problems where
this benchmark is too strong to derive meaningful positive results.
As a result, recently, there has been much research on addressing these
difficulties: two such methods are (a) introducing a stochastic element to the
online arrivals (i.e. the arriving inputs are sampled from a distribution which
the online algorithm may or may not know), and (b) changing the benchmark to
competing against algorithms which also don't know the exact input and only
know as much or as little as the online algorithm. In this talk, we will survey
some recent results on both these methods, using the so-called prophet
inequalities and stochastic knapsack as canonical examples.