Treffer: Average-Case Approximability of Optimisation Problems ; Average-Case Approximierbarkeit von Optimierungsproblemen
Weitere Informationen
Die Dissertation kombiniert Durchschnittskomplexität (Average-Case Complexity) mit der Frage der Approximierbarkeit von Optimierungsproblemen. Beides sind Möglichkeiten mit dem Problem umzugehen, dass viele Berechnungsprobleme nicht mit polynomieller Laufzeitschranke berechenbar sind, es sei denn P = NP. Dafür wird ein theoretischer Rahmen vorgestellt, der sowohl die Klassifizierung von Optimierungsproblemen in Hinblick auf ihre Approximierbarkeit im Durchschnitt als auch die Untersuchung der strukturellen Eigenschaften der entstandenen Average-Case Approximationsklassen gestattet. Anstatt strikte obere Schranken für die Zeit anzugeben, die benötigt wird, um das Wortproblem für Entscheidungsprobleme zu lösen, betrachtet man in der Average-Case Komplexitätstheorie die durchschnittliche Zeit, die für diese Aufgabe benötigt wird. Die durchschnittliche Zeit wird bezüglich einer Wahrscheinlichkeitsverteilung auf den Eingabeinstanzen bestimmt, d.h. durchschnittliche Eigenschaften werden nie für ein Entscheidungsproblem allein angegeben, sondern für ein Entscheidungsproblem kombiniert mit einer Eingabeverteilung: ein randomisiertes Entscheidungsproblem. Bei der Untersuchung der durchschnittlichen Approximierbarkeit von randomisierten Optimierungsproblemen sind nicht nur Approximationsalgorithmen interessant, deren Laufzeit im Durchschnitt polynomiell ist. Bei der Suche nach Approximationsalgorithmen für ein Optimierungsproblem ist man an Algorithmen mit möglichst kleiner Performance Ratio interessiert. Um nun strikte obere Schranken für die Performance Ratio zu durchschnittlichen Schranken abzuschwächen, werden entsprechende Konzepte benötigt, die uns erlauben, Approximierbarkeit mit durchschnittlich konstantem, polynomiellem oder exponentiellem Faktor auszudrücken. Entsprechende Konzepte für durchschnittlich polynomielle und durchschnittlich exponentielle Funktionen sind bereits bekannt, der Begriff der durchschnittlich konstanten Funktionen wird in dieser Arbeit eingeführt. Eine Reihe von Ergebnissen über das ...