LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

GI-Forschungsseminar
Beweisverifikation und Approximationsalgorithmen

Tagungsprogramm


Montag, 21.April 1997

8:50 - 9:00 Begrüßung
9:00 - 10:00 Einführung Komplexitätstheorie und Approximationsalgorithmen (Jansen)
10:00 - 10:15 Kaffeepause
10:15 - 11:15 Randomisierte Algorithmen (Andrzejak)
11:15 - 12:15 Übung
14:30 - 15:30 Derandomisierung (Sieling)
15:30 - 16:00 Kaffeepause
16:00 - 18:00 Beweisverifikation und Nichtapproximierbarkeit (Hougardy)
19:30 - ??:?? Übung/Diskussion

Dienstag, 22.April 1997

9:00 - 10:00 Probabilistisch verifizierbare Beweise I (Heun)
10:00 - 10:15 Kaffeepause
10:15 - 11:15 Probabilistisch verifizierbare Beweise II (Weigand)
11:15 - 12:15 Übung
14:30 - 15:30 Probabilistisch verifizierbare Beweise III (Merkle)
15:30 - 16:00 Kaffeepause
16:00 - 17:00 Parallele MIP(2,1)-Systeme (Skutella, Gröpl)
17:00 - 18:15 Übung

Mittwoch, 23.April 1997

9:00 - 10:00 Approximierbarkeit von APX-Problemen I (Wilke)
10:00 - 10:15 Kaffeepause
10:15 - 11:15 Approximierbarkeit von APX-Problemen II (Seibert)
11:15 - 12:15 Übung
14:30 - ??:?? Ausflug

Donnerstag, 24.April 1997

9:00 - 10:00 Approximierbarkeit von APX-Problemen III (Rick, Röhrig)
10:00 - 10:15 Kaffeepause
10:15 - 11:15 Free-Bit Variante I (Mundhenk)
11:15 - 12:15 Übung
14:30 - 15:30 Free-Bit Variante II (Slobodová)
15:30 - 16:00 Kaffeepause
16:00 - 17:00 Approximierbarkeit von Setcover (Wolff)
17:00 - 18:15 Übung

Freitag, 25.April 1997

9:00 - 10:00 Semidefinite Programmierung I (Hofmeister)
10:00 - 10:15 Kaffeepause
9:00 - 10:00 Semidefinite Programmierung II (Hühne)
11:15 - 12:15 Übung
14:30 - 15:30 PAS für dichte Instanzen (Wolf)
15:30 - 16:00 Kaffeepause
16:00 - 17:00 PAS für geometrische Probleme (Mayr, Schelten)
17:00 - 18:15 Übung


Volker Heun, 1997-04-18