Inhalt

Fortgeschrittene Themen des Algorithmenentwurfs mit wechselnden Schwerpunkten.

Thema des Seminars ist diesmal die Betrachtung von Algorithmen für "schwere Probleme". Wie wir ja aus der Komplexitätstheorie wissen, gibt es zahlreiche algorithmische Probleme die schwer für eine Komplexitätsklasse sind. Das heißt, dass ein effizienter Algorithmus für ein solches Problem effiziente Algorithmen für die gesamte Klasse liefern würde (z.B. NP-schwer, NP-hard) und daher sehr unwahrscheinlich ist. Sehr viele in der Praxis auftretende Probleme haben diese Eigenschaft, die aber dennoch gelöst werden müssen. Verschiedene Techniken wurden dafür entwickelt, die im Seminar betrachtet werden sollen:

-- Approximationsalgorithmen

-- exakte Algorithmen exponentieller Laufzeit im schlechtesten Fall, der aber selten auftritt

-- LP-Relaxierung, dh. Reduktion des Problems auf (ganzzahliges) lineares Programmieren

-- Metaheuristiken, (simulated annealing, genetische Algorithmen)

Zielgruppe

Master-Studierende der Informatik oder Mathematik

Required Background

Course "Höhere Algorithmik" or a comparable course.

Language

The seminar will be in English.

Requirements

The main requirement is a lecture of 70 minutes given by each participant.

A lengthy written seminar workout is not required, just 4 pages pdf summary sent to the instructor before the talk.

Literature

Books:

[CLR] Cormen, Leiserson, Rivest, Stein (2. Aufl.)

Introduction to Algorithms

[JM]

Jansen, Margraf

Approximative Algorithmen und Nichtapproximierbarkeit

[KT] Kleinberg, Tardos

Algorithm Design

[H] Hromkovic

Algorithms for Hard Problems

D. P. Williamson, D.B.Shmoys.

Design of Approximation Algorithms

F.F.Fomin, D.Kratsch,

Exact Exponential Algorithms.

Sowie Spezialliteratur aus Zeitschriften

Vortragsthemen

No meetings on April 26 and May 24 !

1.  Meeting, May 3

Wenli Xu

approximation algorithms, simple examples, definitions

Approximationsalgorithmen
einfache Beispiele, Definitionen    [JM] Kap. 1

2.

May 10

Myrthe Willemsen

Examples, Vertex Cover, Min-Job-Scheduling, Non-Approximability of TSP

Beispiele
Vertex Cover [CLR]
MIN-Job-Scheduling [JM] 6.1
Nichtapproximierbarkeit von TSP

3.

May 17

Viktor Skoblin

Approximation Algorithms for Delta-TSP
Approximationsalgorithmen für Delta-TSP [JM]6.2

4.

May 31

Helmut Alt

Simulated Annealing [KT] 12.1, 12.2

5.

June 7

Rui Zhao

FPTAs
AA. für Knapsack [CLR]

6.

June 14

Fatemeh Tavakkoli

BIN-Packing und Strip-Packing,
aus [JM] Kap. 7

7. June 21

Neda Rajabian

Linear Programming

Lineare Programmierung [CLR] 29.2

8. June 28

Helmut Alt

LP-Relaxation
weighted vertex cover

9. cancelled

Mouadh Khlifi

Exact Algorithms

Exakte Algorithmen
Einführung [FK] Kap.1

10. cancelled

Doruntina Murtezaj

Branching [FK] Kap.2

11. July 12

Mohannad Nouh

Random Walk und SAT [JM] Kap. 10.1 - 10.4.

12. July 19

Hongmiao Wu

FPT
[H] 3.3