Department of Mathematics

Indian Institute of Science

Bangalore 560 012






Ravishankar Krishnaswamy
Affiliation : Microsoft research, Bangalore

Subject Area






Department of Mathematics, Lecture Hall I




03:30 p.m.




April 04, 2016 (Monday)



"Online Stochastic Optimization: Coping with Large Competitive Ratios"


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.