Towards the specification of the class of tractable computing problems

• Applicant: Professor Dr. Juraj Hromkovic
• Subject Area: Theoretical Computer Science
• Term: from 1999 to 2003
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants