312.256 (18S) Combinatorial Optimization

Sommersemester 2018

Registration deadline has expired.

First course session
06.03.2018 08:00 - 09:30 N.2.35 On Campus
... no further dates known

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

List of events is loading...

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

Im Fall von online durchgeführten Prüfungen sind die Standards zu beachten, die die technischen Geräte der Studierenden erfüllen müssen, um an diesen Prüfungen teilnehmen zu können.

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 scheme

Position 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)

Equivalent courses for counting the examination attempts

Sommersemester 2016
  • 312.256 VO Kombinatorische Optimierung (2.0h / 4.0ECTS)
Sommersemester 2014
  • 312.256 VO Kombinatorische Optimierung (2.0h / 4.0ECTS)