MA-INF 1307 - Seminar Advanced Algorithms

Offered by Thomas Kesselheim

Online Algorithms and Optimization under Uncertainty

In this seminar, we cover topics in the area of online algorithms and optimization under uncertainty. That is, algorithms have to make decisions under incomplete information. Many topics are related to the lecture Algorithms and Uncertainty. Ideally you have already taken this lecture or are taking it during the same semester.

If you are interested in the seminar, please contact Thomas Kesselheim.

Example List of Topics

  • Online Stochastic Matching: Beating 1-1/e, Jon Feldman, Aranyak Mehta, Vahab Mirrokni, S. Muthukrishnan, FOCS 2009
  • Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching, Nikhil R. Devanur, Kamal Jain, Robert D. Kleinberg, SODA 2013
  • Combinatorial Auctions via Posted Prices, Michal Feldman, Nick Gravin, Brendan Lucier, SODA 2015
  • Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays, Yossi Azar, Ashish Chiplunkar, Haim Kaplan, SODA 2017
  • Online service with delay, Yossi Azar, Arun Ganesh, Rong Ge, Debmalya Panigrahi, STOC 2017

Page Tools