Time:

Thursday, 10:00 am (s.t.) to 12 am

First meeting:

First Thursday of the winter 2013/14 term, i.e., 17th of October.

Room:

024 on the ground floor of the MPI building (E1.4)

Prerequisites:

You should bring a solid background in algorithms and data structures. This is an advanced seminar. The papers are challenging and a proper preparation of your talk will require some effort.
The target audience of this reading group are master students and advanced bachelor students.

Content:

In each session we have at most two paper presentations (each 45 minutes + discussion).
Students aiming to get credits give a regular talk and write a short summary about the paper.

Credits:

You earn the usual 7 credit points for a seminar if you (i) give a regular presentation of the paper given to you, and (ii) write a short summary (about 5 pages).

News for students:

 If you want credit for the course, please register with Marvin by sending him a short mail ([first name]@mpiinf.mpg.de) before October 24. Please also specify a paper that you want to present. (Feel free to register even if you did not attend the introductory lecture.)

Schedule:

Date 
Speakers 
Topic 
Oct 17

Martin

Introduction to the seminar

Jan 16

Manoj, Daniel

Stochastic Analyses for Online Combinatorial Optimization Problems An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions

Jan 23

Nicolas,
Patrick

Smoothed Analysis of the kmeans method
Smoothed Analysis of the Successive Shortest Path Algorithm


References for talks:

 [Talk by Manoj]: "Stochastic Analyses for Online Combinatorial Optimization Problems" by N. Garg, A. Gupta, S. Leonardi, P. Sankowski. (SODA, 2008)
 [Talk by Daniel]:
"An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions" by T. Kesselheim, K. Radke, A. Tönnis, B. Vöcking. (ESA, 2013)
 [Talk by Nicolas]:
"Smoothed Analysis of the kmeans method" by D. Arthur, B. Manthey and H. Röglin. (J. ACM, 2011)
 [Talk by Patrick]:
"Smoothed Analysis of the Successive Shortest Path Algorithm" by T. Brunsch, K. Cornelissen, B. Manthey and H. Röglin. (SODA, 2013)

Available papers:

Smoothed Analysis
"Smoothed Analysis of the kmeans method" by D. Arthur, B. Manthey and H. Röglin. (J. ACM, 2011)

"Worst Case and Probabilistic Analysis of the 2Opt Algorithm for the TSP" by M. Englert, H. Röglin und B. Vöcking. (SODA, 2007)
Journal version to appear in Algorithmica
"Smoothed Analysis of the Successive Shortest Path Algorithm" by T. Brunsch, K. Cornelissen, B. Manthey and H. Röglin. (SODA, 2013)

"Smoothed analysis of the condition numbers and growth factors of matrices" by A. Sankar, D. Spielman, S.H. Teng. (SIAM J. Matrix Analysis and Appl., 2006)

"Smoothed analysis of algorithms: The simplex algorithm usually takes polynomial number of steps" by D. Spielman, S.H. Teng. (J. ACM, 2004)

"Smoothed Analysis of Multiobjective Optimization" by H. Röglin, S.H. Teng (FOCS, 2009)
Secretary Problems

"Matroid Secretary for Regular and Decomposable Matroids" by M. Dinitz, G. Kortsarz. (SODA, 2013)

"Improved competitive ratio for the matroid secretary problem" by S. Chakraborty, O. Lachish. (SODA, 2012)
"An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions" by T. Kesselheim, K. Radke, A. Tönnis, B. Vöcking. (ESA, 2013)

"Asymptotically optimal algorithm for stochastic adwords" by N. Devanur, B. Sivan, Y. Azar. (EC, 2012)
Stochastic Online Optimization and PriorIndependent Mechanism Design

"Matroid Prophet Inequalities" by R. Kleinberg, M. Weinberg. (STOC, 2012)

"Revenue maximization with a single sample" by P. Dhangwatnotai, T. Roughgarden, Q. Yan. (EC, 2010)

"Online and Stochastic Survivable Network Design" by A. Gupta, R. Krishnaswamy, R. Ravi. (SIAM J. on Computing, 2012)
"Stochastic Analyses for Online Combinatorial Optimization Problems" by N. Garg, A. Gupta, S. Leonardi, P. Sankowski. (SODA, 2008)
