Probabilistic Analysis of Algorithms

General Information

When Where Start CP Lecturer
L2Wednesday, 10:25 - 11:55LBH / E.08April 172.5Röglin
E2Thursday, 12:30 - 14:00LBH / E.08April 183.5Reichel, Röglin


In this lecture we will discuss several recent results in the area of smoothed analysis of algorithms. The topics will be similar in flavor to the second part of last semester's lecture Pearls of Algorithms. However, it is not required to have attended that lecture.

Date Contents Course Materials
April 171 Introduction to Smoothed AnalysisSlides
April 242 Mathematical Background
3 Multiobjective Optimization
Lecture Notes (Chapters 1.2 and 3)
May 83.1 The Knapsack ProblemLecture Notes (Chapter 3)
May 153.1 The Knapsack Problem (cont'd)Lecture Notes (Chapter 3)
June 53.2 Lower Bound for the Number of Pareto-optimal Solutions[BV04] (Section 4)
June 124 Successive Shortest Path Algorithm[BCMR13]
June 19Discussion of Problem Set 6
June 264 Successive Shortest Path Algorithm (cont'd) \\5 k-Means MethodSlides
July 35 k-Means Method (cont'd)[AV06]
July 105 k-Means Method (cont'd)[AV06]
July 176 2-Opt Algorithm for the TSP[ERV07] (Section 4.1)

Problem Sets


Oral exams can be taken on July 22 and August 14, 15, and 16. Please send an email to Mrs. Bertram to schedule the exam.


en/lehre/ss13/robabilistic-analysis-algorithms.txt · Zuletzt geändert: 2014/03/21 16:24 (Externe Bearbeitung)