Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Linear Programming and Combinatorial Optimization

MSc Lecture - Winter 2022/23

It is important that all participants subscribe to our course moodle. There we will announce all organizational details. Note that the moodle subscription is additionally required to the official course subscription via the Studienreferat.

Description

The main paradigm in the course will be the design and analysis of algorithms for combinatorial optimization. We will cover problems that can be solved optimally in polynomial time (matchings, flows, min-cost flows) as well as study problems that are NP-hard, and for which we can develop approximation algorithms. Linear programming techniques will be one of the central themes of the course. We will learn to model optimization problems as linear and integer programs, and develop the techniques to solve them. 

Tentative list of topics: 

Basics of linear programming, Duality, Matchings (Hall's Theorem, Tutte's Theorem), Vizing's Theorem, Weighted Matching Algorithms, Matroids, Spanning Trees and Arborescences, Network Flow, Approximation Algorithms (Rounding, Primal-Dual Method), Multicommodity Flows and Cut Problems.

You can take a look at the previous edition of the course in moodle, to get a better understanding of the topics.

Organization

The course will be held in person and will consist of lectures and problem solving sessions. Lecture and exercise dates will be decided as needed.

Students are required to hand in homework every couple of weeks. At the end of the course there will be a written final examination. At least 50% points are required in homework assignments for admission to the final examination. Final grade will be decided on the basis of performance in the written exam (60%) and homework assignment (40%).

Requirements

There are no formal requirements, but we expect the students to have the ability to understand/write mathematical proofs and have basic familiarity with algorithms.

Dates

We will meet weekly on Tuesdays and Thursdays from 11:00 to 12:30.

Lecture Team

The following persons are involved in this lecture:

Dr. Davis Issac

Lecturer

Office: K-2.07 E-Mail: Davis.Issac(at)hpi.de

Dr. Nikhil Kumar

Lecturer

Office: K-2.07 Email: Nikhil.Kumar(at)hpi.de