TY  - THES
AB  - 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.
AU  - Brauer, Sascha
CY  - Paderborn
DA  - 2019
DO  - 10.17619/UNIPB/1-816
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 25.09.2019
N1  - Universität Paderborn, Dissertation, 2019
PB  - Veröffentlichungen der Universität
PY  - 2019
SP  - 1 Online-Ressource (xi, 152 Seiten)
T2  - Institut für Informatik
TI  - Classification and approximation of geometric location problems
TT  - Klassifikation und Approximation von Problemen der Geometrischen Platzierung
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-35745
Y2  - 2026-01-10T07:15:52
ER  -