312.256 (18S) Combinatorial Optimization
Overview
- Lecturer
- Course title german Kombinatorische Optimierung
- Type Lecture
- Hours per Week 2.0
- ECTS credits 4.0
- Registrations 14
- Organisational unit
- Language of instruction German
- possible language(s) of the assessment German
- Course begins on 06.03.2018
Time and place
Course Information
Intended learning outcomes
Fortgeschrittene Kenntnisse im Gebiet Kombatorische Optimierung
Teaching methodology including the use of eLearning tools
Vortrag im Hörsaal, eigenständiges Erarbeiten von Aufgaben
Course content
- Optimierungsaufgaben auf bipartiten Graphen (Matchingtheorie, Zuordnungsproblem, Gale-Shapley Matching, Stundenplanproblem)
- Linerare Algebra und Graphen (Kreise und Schnitte in Graphen, Matrix-Baum Satz, elektrische Netzwerke, Eigenwertschranken)
- Knotenfärbung auf Intervallgraphen
- Approximationsalgorithmen (Baumheuristiken für das Rundreiseproblem, Scheduling, Mengenüberdeckungsprobleme)
- Approximation mittels konvexer Optimierung (Goemans-Williamson Rundungsheuristik für Max-Cut, Graphfärben)
Prior knowledge expected
Lineare Algebra (Basis, Dimension, lineare Gleichungen, Eigenwerte), Diskrete Mathematik
Literature
B. Korte und J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer 2000.
D. Jungnickel, Graphs, Networks and Algorithms, Springer, 1999
Examination information
Examination methodology
Am Ende der LV findet eine schriftliche Klausur statt.
Examination topic(s)
Inhalt der LV
Assessment criteria / Standards of assessment for examinations
Erfolgreich abgeschlossene Abschlussprüfuing
Grading scheme
Grade / Grade grading schemePosition in the curriculum
- Master's degree programme Technical Mathematics
(SKZ: 401, Version: 13W.1)
-
Subject: Diskrete Mathematik
(Compulsory elective)
-
Kombinatorische Optimierung (
2.0h VO / 4.0 ECTS)
- 312.256 Combinatorial Optimization (2.0h VO / 4.0 ECTS)
-
Kombinatorische Optimierung (
2.0h VO / 4.0 ECTS)
-
Subject: Diskrete Mathematik
(Compulsory elective)