Seminar at SMU Delhi

How do we make decisions without knowledge of the future? How do you decide between paying Rs 1000 for the monthly membership to the swimming pool and paying-per-swim at Rs 100/swim? This talk will explore the area of "Online Algorithms" where the input to the algorithm is revealed one step at a time and the algorithm has to make decisions while hedging against the future. The lack of information - about the future - can often be offset by "resource augmentation" and we shall demonstrate this through examples from the world of scheduling.