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.

If you are interested in the seminar, please come to the introductory meeting. It will take place on Monday, April 16, at 16:15 in room 2.050 in the computer science building (Endenicher Allee 19a). If this is not possible, or in case of any questions, please contact Thomas Kesselheim. We will agree on a time slot for a weekly meeting there (possibly Mondays at 16:15) and assign the topics.

Preliminary 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