Seminars and Colloquia
Mathematics
Online algorithms with recourse
Tue, Jun 20, 2017,
04:00 PM to 05:00 PM
at Madhava Hall
Professor Amit Kumar
IIT Delhi
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, graph algorithms and other
classical problems, I will show that one can get interesting results
in this ''online algorithms with recourse'' model.
