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
über
Beweisverifikation und Approximationsalgorithmen

Kurzbeschreibung:

Dieses Seminar über Beweisverifikation und Approximationsalgorithmen ist für interessierte Diplomanden, Doktoranden bzw. promovierte Nachwuchswissenschaftler gedacht, die sich aktiv einen Überblick über dieses Thema verschaffen wollen. In diesem Seminar sind noch Plätze zu vergeben.

Detailliertere Informationen werden im folgenden gegeben. Einen einführenden Artikel zu diesem Thema findet man als ein Kapitel der Autoren Prömel und Steger im Buch:

Inhalt:

Die Entwicklung probabilistisch verifizierbarer Beweise und die Konsequenzen daraus sind einer der spektakulärsten Fortschritte der theoretischen Informatik in den letzten Jahren. Zu den Konsequenzen gehören insbesondere die rasanten Fortschritte bei der Klassifizierung der Approximierbarkeit kombinatorischer Optimierungsprobleme, die auch den zentralen Aspekt dieses GI-Seminars darstellen.

Die Charakterisierung von NP durch probabilistisch verifizierbare Beweise führt zu sogenannten robusten oder gap-bildenden Reduktionen und damit letztendlich zu Nicht-Approximierbarkeitsresultaten. In den letzten Jahren wurden andererseits aber auch einige spektakuläre "positive" Ergebnisse erzielt, allen voran die Entwicklung eines polynomialen Approximationsschemata für das euklidische TSP. Zusammen ergeben sich daraus nunmehr für eine ganze Reihe von kombinatorischen Optimierungsproblemen untere und obere Schranken für die in polynomialer Zeit erreichbare Approximationsgüte, die im wesentlichen übereinstimmen. Hierzu zählen etwa die Chromatische Zahl, Set-Covering und das Max-Cut-Problem.

Im diesem Seminar stellen wir zum einen die grundlegenden Ansätze und Ideen zum Beweis von unteren Schranken mittels probabilistisch verifizierbarer Beweise vor und diskutieren zum anderen ausführlich die neuen Techniken und Algorithmen, die zu den verbesserten oberen Schranken geführt haben.

Themenbereiche:

* Probabilistisch verifizierbare Beweise
* Nicht-Approximierbarkeit, ausgewählte Beispiele
* Approximationsklassen
* Randomisierte Approximationsalgorithmen
* Derandomisierung, ausgewählte Beispiele
* Dichte Instanzen
* Geometrische Probleme

Durchführung:

Die Teilnehmer werden Originalarbeiten erhalten, über die sie in Vorträgen im Seminar berichten werden. Die Leitung des Seminars wird von: übernommen.

Hintergrund und Teilnehmerkreis:

Die Gesellschaft für Informatik (GI) veranstaltet seit kurzem Seminare zu aktuellen Forschungsthemen, die noch keine angemessene Darstellung in der Lehrbuchliteratur gefunden haben. Diese Seminare sollen in der Forschung tätigen jungen Wissenschaftlern, Diplomanden, Doktoranden und promovierten Nachwuchswissenschaftlern die Möglichkeit geben, wichtige neue Entwicklungen in der Informatik kennenzulernen.

Teilnahmekriterien:

Für die Teilnahme sind keine Vorkenntnisse im Bereich des Seminarthemas notwendig, sondern nur eine sehr gute wissenschaftliche Qualifikation ist erforderlich. Die Auswahl der Teilnehmer findet aufgrund einer Bewerbung statt, die Informationen über den wissenschaftlichen Werdegang des Bewerbers und die Empfehlung durch einen Hochschullehrer enthält.

Seminarort und Zeit:

Das Seminar wird im Forschungsinstitut für Informatik in Schloß Dagstuhl vom 21. mit 26. April diesen Jahres stattfinden. Das dortige Institut bietet aufgrund seiner hervorragenden Bibliothek und seiner besonderen Atmosphäre eine ideale Umgebung für dieses Seminar.

Bewerbung:

Bewerbungen und Anfragen zu diesem Seminar werden bis zum 01.02.97 an folgende Adresse erbeten:
Volker Heun, 1996-11-05, 1997-01-22