Probabilistic Analysis of Algorithms

General Information

	When	Where	Start	CP	Lecturer
L2	Wednesday, 10:25 - 11:55	LBH / E.08	April 17	2.5	Röglin
E2	Thursday, 12:30 - 14:00	LBH / E.08	April 18	3.5	Reichel, Röglin

Date	Contents	Course Materials
April 17	1 Introduction to Smoothed Analysis	Slides
April 24	2 Mathematical Background 3 Multiobjective Optimization	Lecture Notes (Chapters 1.2 and 3)
May 8	3.1 The Knapsack Problem	Lecture Notes (Chapter 3)
May 15	3.1 The Knapsack Problem (cont'd)	Lecture Notes (Chapter 3)
June 5	3.2 Lower Bound for the Number of Pareto-optimal Solutions	[BV04] (Section 4)
June 12	4 Successive Shortest Path Algorithm	[BCMR13]
June 19	Discussion of Problem Set 6
June 26	4 Successive Shortest Path Algorithm (cont'd) 5 k-Means Method	Slides
July 3	5 k-Means Method (cont'd)	[AV06]
July 10	5 k-Means Method (cont'd)	[AV06]
July 17	6 2-Opt Algorithm for the TSP	[ERV07] (Section 4.1)

[Ro11] Heiko Röglin.
Lecture Notes: Pearls of Algorithms.
University of Bonn, Winter 2011/12.
[BV04] Rene Beier and Berthold Vöcking.
Random Knapsack in Expected Polynomial Time.
Journal of Computer and System Sciences 69(3): 306-329 (2004).
[BCMR13] Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey, and Heiko Röglin.
Smoothed Analysis of the Successive Shortest Path Algorithm. \\In Proc. of the 24th SODA, pp. 1180-1189, 2013.
[AV06] David Arthur and Sergei Vassilvitskii.
Worst-case and Smoothed Analyses of the ICP Algorithm, With an Application to the k-means Method.
In Proc. of the 47th FOCS, pp. 153-164, 2006.
[ERV07] Matthias Englert, Heiko Röglin, and Berthold Vöcking.
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP.
In Proc. of the 18th SODA, pp. 1295-1304, 2007.