Online Decision-Making with Samples
While analyzing algorithms in the worst case has long served us well, recent years have seen an exciting surge in analyzing algorithms in models that go beyond the worst case. We consider some classical problems in sequential decision-making, like network design and load-balancing and set cover. (E.g., in load balancing, jobs arrive online and must be assigned to machines to minimize the maximum load of any machine.) For these problems, can we get results better than the adversarial setting if we have a small sample of the upcoming data? I will try to make this talk as self-contained as possible.
This is based on older work with C.J. Argue, Alan Frieze, Chris Seiler, and more recent work with Marco Molinaro.
Bio: Anupam Gupta is a Silver Professor in the Department of Computer Science at the Courant Institute of Mathematical Sciences at New York University. His research interests are in the design and analysis of algorithms, specifically in decision-making under uncertainty, in approximation algorithms, and algorithmic theory of metric spaces. He is a Fellow of the ACM and has been recognized by an Alfred Sloan Fellowship and the Herb Simon Award for Teaching Excellence at Carnegie Mellon.