Approximation Algorithms

Modulnummer: Q06-20
Englischer Titel: Approximation Algorithms
Leistungspunkte: 6
Lehrperson: Kratsch

Empfohlene Vorkenntnisse

Solide Grundkenntnisse zu Algorithmen und Komplexität.

Zwingende Voraussetzungen

keine

Inhalt

Many relevant computational problems are by nature not decision but optimization problems, in the sense that one does not simply want a yes or no answer, but is instead interested in finding a best among a set of possible solutions. Famous examples of such problems are scheduling, facility location, or knapsack. Efficient computation of an optimum solution to such problems is often very difficult, usually testified by the NP-hardness of their underlying decision problems. This does however not exclude efficient computation of good solutions by so-called approximation algorithms.

This lecture is about the design and analysis of approximation algorithms. We will discuss standard methods like greedy, local search, cost scaling, etc. and how to generally assess the quality of approximations. Further, we will learn about special types of reductions to transfer approximation results between different optimization problems. Such reductions will also be used to show limitations of approximation algorithms.

Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung

- schriftlich eingereichte und/oder mündlich vorgetragene Lösungen zu Aufgaben

Lehrveranstaltungen

Vorlesung: 3 SWS
Übung: 1 SWS

Zugeordneter Vertiefungsschwerpunkt

Algorithmen und Modelle: ja
Modellbasierte Systementwicklung: nein
Daten- und Wissensmanagement: nein
Ohne Vertiefungsschwerpunkt: nein

Sprache im Modul

Deutsch: nein
Englisch: ja

Angeboten für Studiengänge

M. Sc.: ja
M. Ed.: ja
Wirtschaftsmaster: ja

Angeboten im

Wintersemester: nein
Sommersemester: ja

Turnus

Alle zwei Jahre