Sie befinden sich hier: Forschung » Research » Teaching » Summer Term 2013 » Probabilistic Analysis of Algorithms

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 |

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 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) |

- Problem Set 1 (to be discussed on April 18)
- Problem Set 2 (to be discussed on April 25)
- Problem Set 3 (to be discussed on May 2)
- Problem Set 4 (to be discussed on May 16)
- Problem Set 5 (to be discussed on June 6)
- Problem Set 6 (to be discussed on June 13)
- Problem Set 7 (to be discussed on June 27)
- Problem Set 8 (to be discussed on July 4)
- Problem Set 9 (to be discussed on July 11)

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.

- [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.

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