Abstract
Online algorithms model situations where the input data arrives over time, and the algorithm needs to take decisions without knowing the future input. They are typically analyzed in the framework of competitive analysis -- the performance of such an algorithm is compared against an adversary which knows the entire future beforehand. Although this has been a very fruitful approach, it often leads to pessimistic results because the adversary is much more powerful than the online algorithm. Recently, there have been attempts to evolve alternate ways of analyzing online algorithms which give more power to the online algorithm (as compared to the offline adversary). I will discuss some recent work on models which allow the algorithm to change a small number of decisions taken in the past. Drawing from examples in scheduling and graph algorithms, I will show that one can get interesting results in this ''online algorithms with recourse'' model.