~~NOTRANS~~

# Probabilistic Analysis of Algorithms

## Lecture

When Where Start Lecturer
Monday, 10:15-11:45 LBH / Hörsaal III.03a April 13 Röglin

Due to popular demand, the lecture will start at 10:15.

## Contents

The theory of algorithms has traditionally focused on worst-case analysis. This focus has led to both a deep theory and many beautiful and useful algorithms. There are, however, a number of important problems and algorithms for which worst-case analysis does not provide useful or empirically accurate results. One prominent example is the simplex method for linear programming whose worst-case running time is exponential while in fact it runs in near-linear time on almost all inputs of interest. Another example is the knapsack problem. While this problem is NP-hard, it is a very easy optimization problem in practice and even very large instances with millions of items can be solved efficiently. The reason for this discrepancy between worst-case analysis and empirical observations is that for many algorithms worst-case instances have an artificial structure and hardly ever occur in practical applications.

In this lecture we will introduce the concept of smoothed analysis. In such an analysis one does not study the worst-case behavior of an algorithm but its (expected) behavior on random or randomly perturbed inputs. We will prove, for example, that there are algorithms for the knapsack problem whose expected running time is polynomial if the profits or weights are slightly perturbed at random. This shows that instances on which these algorithms require exponential running time are fragile with respect to random perturbations and even a small amount of randomness suffices to rule out such instances with high probability. Hence, it can be seen as an explanation for why these algorithms work well in practice. We will also apply smoothed analysis to the simplex method, clustering problems, the traveling salesman problem, etc.

Date Contents Course Materials
April 131 Introduction to Smoothed Analysis Slides
April 202 Probability Theory
3 Knapsack Problem and Multiobjective Optimization
3.1 Nemhauser-Ullmann Algorithm
Lecture Notes
April 273.2 Number of Pareto-optimal Solutions
3.2.1 Upper Bound
Lecture Notes
May 43.2.2 Lower Bound
3.3 Multiobjective Optimization
Lecture Notes
May 113.4 Core Algorithms Lecture Notes
May 184 Smoothed Complexity of Binary Optimization Problems Lecture Notes
June 14 Smoothed Complexity of Binary Optimization Problems (continued)
5 Successive Shortest Path Algorithm
5.1 The SSP Algorithm
5.2 Smoothed Analysis
Lecture Notes
Slides
June 85.3 Proof of Theorem 5.2 Lecture Notes
Slides
June 155.3 Proof of Theorem 5.2 (cont'd)
6 The 2-Opt Algorithm for the TSP
6.1 Overview of Results
Lecture Notes
Slides
June 226.2 Polynomial Bound for f-Perturbed Graphs
6.3 Improved Analysis
Lecture Notes
Slides
June 297 The k-Means Method
7.1 Potential Drop in an Iteration of k-Means
7.2 Iterations with Large Cluster Changes
Lecture Notes
July 67.3 Iterations with Small Cluster Changes
7.4 Proof of Theorem 7.1
Lecture Notes

## Tutorials

When Where Start
Tuesday, 14:30-16:00 LBH / Room E.08 April 21

## Exams

Even though there is no formal requirement to participate in the tutorials and to submit the homework problems, it is strongly recommended to do so. Oral exams can be taken on July 16, August 5, and August 6. Please schedule your exam with Antje Bertram until June 30. The re-exams will be on September 30.