Summer 2019

Approximation Algorithms

Master Course in Summer 2019
03-ME-602.99a, 6 CP

A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be modeled as combinatorial optimization problems. In most cases, these problems are computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide a worst case guarantee on the performance in comparison to the optimum solution. In this course, we shall study algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on performance. The course aims at developing a toolkit for solving such problems. The lectures will consist of designing polynomial-time algorithms and proving rigorous bounds on their worst case performances.

Lecturers:

• Prof. Dr. Nicole Megow
• Dr. Martin Böhm
• Dr. Ruben Hoeksma

Time & Room:

• Tue 12-14 in room MZH 6210
• Thu 12-14 in room MZH 6210

Start:

• Tuesday, April 2, 2019

Examination:

• The examination will be by individual oral exam. A 1/3 mark bonus is awarded to students who correctly solve 60% of the homework exercises.

Literature: The course is based on parts of the literature below and recent research articles that will be added later.

• [WS] The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys online version
• [V] Approximation Algorithms, Vijay V. Vazirani
• [GM] Approximation Algorithms and Semidefinite Programming, Bernd Gärtner and Jiří Matoušek, Springer, 2012.

Diskrete Strukturen: Kombinatorik, Graphen, Färbungen

Proseminar im Sommersemester 2019
03-BE-699.13, 4 CP (+1 CP bei Zusatzleistung)

Das Seminar behandelt grundlegende Fragestellungen, Techniken und Resultate zu diskreten Strukturen. Zu den Themen gehören Kombinatorik, Induktion, Graphen, Bäume, Färbungen und Matchings. Beispiele für Fragestellungen sind:

• Wie färbt man eine Landkarte mit wenigen Farben so dass benachbarte Länder verschiedene Farben haben?
• Wie erhält man eine maximale Anzahl von Paaren (z.B. Zuordnungen von Arbeitnehmern und Arbeitgebern)?
• Welche grundlegenden Möglichkeiten gibt es, kombinatorische Beweise zu führen?
• Wie sortiert man eine Menge von Zahlen?
• Wie zählt man Bäume?

Die Seminarvorträge werden in einer 1-2 tägigen Blockveranstaltung am Ende des Semesters bzw. am Beginn der Semesterferien gehalten. Details, Termine und Themen werden in der Vorbesprechung abgestimmt.

Dozent:

• Prof. Dr. Nicole Megow

Termin:

• Mittwoch, 3. April 2019, 14:00-15:00 im MZH 3150 (einmalig), Vorbesprechung und Themenvergabe

Literaturgrundlage:

• Lovász, Pelikan, Vesztergombi: Diskrete Mathematik, Springer 2005
• Beutelspacher, Zschiegner: Diskrete Mathematik für Einsteiger, Vieweg-Teubner, 4. Auflage, 2011
• Steger: Diskrete Strukturen 1, Springer, 2002

Hands-on Tutorial on Optimization (engl./dt.)

Block course in Summer 2019 (Sep 23–27)
03-BE-699.12, 3 CP

A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be formulated as discrete linear optimization problems. This course briefly introduces the theory of such problems.

We develop a toolkit to model real-world problems as (discrete) linear programs. Some examples of basic optimization problems that are part of this toolkit are scheduling, packing, matching, routing, and network-design. We also explore different ways to find integer solutions such as cutting planes, Branch & Bound, and column generation. Based on this theoretical background, we focus on translating practical examples into mixed-integer linear programs. We learn how to use professional solvers (such as CPLEX, Gurobi, and FICO Xpress) and tailor the solution process to certain properties of the problem.

Throughout the course, we concentrate on modeling and solving practical problems with some theory parts in between.

Lecturers:

• Prof. Dr. Nicole Megow
• Dr. Ruben Hoeksma
• Dr. Franziska Eberle

This course consists of two phases:

• One week of lectures and practical labs during Mon Sept 23 – Fri Sept 27 from 9:00 to 12:30 and from 13:30 to 17:00 in room MZH 6210.
• One project has to be modeled, implemented, and solved individually or in a group of at most two students. The topic will be either developed with or provided by the lecturers. The project including the implementation has to be presented at the latest in the first week of the winter semester 2019/2020.

There are no prerequisites except some basic programming skills to participate.