Details

Autor(en) / Beteiligte

• Brauer, Sascha
• Blömer, Johannes[Akademischer Betreuer]
• Röglin, Heiko[Akademischer Betreuer]

Titel

Classification and approximation of geometric location problems : = Klassifikation und Approximation von Problemen der Geometrischen Platzierung

Ort / Verlag

Paderborn

Erscheinungsjahr

2019

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 25.09.2019
• ger: In dieser Arbeit untersuchen wir komplexitätstheoretische Aspekte und Algorithmen mit garantierter Approximationsgüte für verschiedene Probleme der geometrischen Platzierung. Der Fokus liegt dabei auf dem Fuzzy k-Means Problem, welches bisher nicht substantiell theoretisch untersucht wurde. Wir zeigen, dass eine Variante von Discrete Fuzzy k-Means auf metrischen Räumen, sowie eine hier neu definierte Radiusvariante dieses Problems, NP-schwer sind. Eine beliebte algorithmische Herangehensweise an diese Probleme ist die single-swap Heuristik. Dieser lokale Suchalgorithmus tauscht iterativ einen Repräsentanten der aktuellen Lösung gegen einen anderen Kandidatenpunkt, bis eine stabile Lösung gefunden wird. Wir beweisen, dass dieser Algorithmus für verschiedene Probleme streng PLS-vollständig ist. Das heißt, dass im worst-case exponentiell viele Iterationen benötigt werden, bis eine single-swap Suche terminiert. Anschließend zeigen wir, dass optimale Lösungen des allgemeinen Fuzzy k-Means Problems nicht durch Radikale über den rationalen Zahlen lösbar sind. Es gibt also Instanzen, deren optimale Lösungen nicht durch eine endliche Verkettung rationaler Zahlen durch die Grundrechenarten und das Ziehen von Wurzeln dargestellt werden können. Folglich kann jeder Algorithmus, der versucht, das Problem zu lösen, höchstens eine approximativ optimale Lösung finden. Wir präsentieren einen Algorithmus, der das Fuzzy k-Means Problem mit Faktor (1+epsilon) approximiert. Dieser Algorithmus stellt eine Verbesserung bisher bekannter Algorithmen dar, da seine Laufzeit unabhängig von der Gewichtung der Eingabepunkte ist und die exponentielle Abhängigkeit von der Anzahl an Clustern linear ist.
• eng: In this thesis we explore aspects of computational complexity and algorithms with a guaranteed approximation ratio for several geometric location problems. The main focus is on the Fuzzy k-Means problem, a problem that has so far not been subject of a substantial theoretical analysis. We show that a variant of Discrete Fuzzy k-Means on metric spaces, as well as a newly defined radius variant of that problem, are NP-hard. A popular algorithmic approach to these problems is the single-swap heuristic. This local search algorithm iteratively swaps a single representative for another candidate until it finds a stable solution. We prove that this algorithm is tightly PLS-complete for several problems. This means that, in the worst case, it takes an exponential number of iterations until a single-swap local search terminates. Afterwards we show that optimal solutions of the general Fuzzy k-Means problem are not solvable by radicals over the rational numbers. Thus, there are instances where optimal solutions cannot be represented by a finite concatenation of rational numbers using elementary arithmetic and extracting roots. In consequence, any algorithm trying to solve the problem can at most find an approximately optimal solution. We present an algorithm approximating the Fuzzy k-Means problem with a factor of (1 + epsilon). Our algorithm improves previously presented algorithms as its runtime is independent of any weight of the input points and the exponential dependence on the number of clusters is linear.