Modul

The module will be completed by an oral exam (ca. 30 min). 

The students

• know basic problems of combinatorial optimization as discussed in the lectures and are able to explain them,
• know typical methods for the probabilistic analysis of algorithms and combinatorial optimization problems and are able to use them for the solution of specific optimization problems,
• are familiar with the essential techniques of proof and are able to explain them,
• know how to work in a self-organized and self-reflexive manner.

none

This course is devoted to the analysis of algorithms and combinatorial optimization problems in a probabilistic framework. A natural setting for the investigation of such problems is often provided by a (geometric) graph. For a given system (graph), the average or most likely behavior of an objective function of the system will be studied. In addition to asymptotic results, which describe a system as its size increases, quantitative laws for systems of fixed size will be described. Among the specific problems to be explored are

• the long-common-subsequence problem,
• packing problems,
• the Euclidean traveling salesperson problem,
• minimal Euclidean matching,
• minimal Euclidean spanning tree.

For the analysis of problems of this type, several techniques and concepts have been developed and will be introduced and applied in this course. Some of these are

• concentration inequalities and concentration of measure,
• subadditivity and superadditivity,
• martingale methods,
• isoperimetry,
• entropy.

It is recommended to have taken the module `Probability Theory' from the Bachelor program beforehand.

Total workload: 240 hours

Attendance: 90 hours

• lectures, problem classes, and examination

Self-studies: 150 hours

• follow-up and deepening of the course content
• work on problem sheets
• literature study and internet research related to the course content
• preparation for the module exam.