Zur Spezifikation der Klasse praktisch lösbarer algorithmischer Aufgaben

• Antragsteller: Professor Dr. Juraj Hromkovic
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 1999 bis 2003
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5209054

Unser Ziel ist es, zur Forschung auf diesem Gebiet durch ein neues Konzept und eine Änderung der bisherigen Schwerpunkte beizutragen. Das neue Konzept, das wir für dieses Projekt vorschlagen, baut auf der Einführung des Begriffes der Stabilität der Approximation auf. Die Idee basiert auf der Beobachtung, daß die Berechnungsschwierigkeit vieler Optimierungsaufgaben stark von der Menge der zulässigen Eingaben abhängt. Informal ausgedrückt, ist ein Approximationsalgorithmus für eine Eingabemenge L stabil bezüglich eines Entfernungsmaßes M, falls er auch ein Approximationsalgorithmus für eine Eingabemenge Le ist, wobei Le alle Eingaben aus L und alle diejenigen Eingaben enthält, die sich bezüglich M nicht viel von Eingaben aus L unterscheiden. Dieses Konzept ermöglicht das Erzielen positiver und auch negativer Resultate und trägt zu einer genaueren Ermittlung der Grenze zwischen praktisch lösbaren und praktisch unlösbaren Aufgaben bei.

• DFG-Verfahren: Sachbeihilfen