IISER Pune
INDIAN INSTITUTE OF SCIENCE EDUCATION AND RESEARCH (IISER) PUNE
where tomorrow’s science begins today
An Autonomous Institution, Ministry of Human Resource Development, Govt. of India
Links
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.
 

homecolloquia_seminars