Modulcode:	infDO-01a
Englische Bezeichnung:	Discrete Optimization
Modulverantwortliche(r):	Dr. Max Deppert
Turnus:	unregelmäßig (WS19/20 SS24)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	30 Std. Vorlesung, 30 Std. Präsenzübung, 120 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	WI (BSc Inf (15)) TI (MSc Inf (15)) WI (MSc Inf (15)) WI (MSc WInf (15))
Lehrsprache:	Englisch
Voraussetzungen:	Inf-Math-A Inf-Math-B Inf-Math-C infBL-01a infAAK-01a

Kurzfassung:

This lecture gives an introduction to discrete optimization. We discuss algorithms and structural properties for several graph problems as well as packing problems. Furthermore, we consider powerful tools that are used to model problems in discrete and combinatorial optimization and analyze their complexity and their expressive strength.

Lernziele:

Participants of this course will learn algorithmic approaches on how to solve discrete optimization problems. They will obtain an understanding of the complexity of the problems and the limitations of the presented methods.

Lehrinhalte:

Main topics of this course are: Matching in bipartite and non-bipratite graphs, matroid optimization, flows and cuts, polyhedral combinatorics, linear programming and duality, algorithms for packing problems.

Weitere Voraussetzungen:

• A course in algorithms and data structures.
• Basic knowledge about linear algebra

Prüfungsleistung:

Depending on the expected number of examinees there will be a written or oral exam at the end of the semester.

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

• B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics 21 Springer, Berlin Heidelberg New York, 2012.
• W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver, Combinatorial Optimization.
• C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982.

Verweise:

Kommentar: