Clustering

Das Clustering Problem besteht darin, m Punkte im n-dimensionalen Raum jeweils einem von k Zentralpunkten so zuzuordnen, so daß die Summe der Abstände der Punkte von ihren zugeordneten Zentralpunkten minimiert wird. Dieses Problem hat eine Fülle von Anwendungen wie zum Beispiel in der Schrifterkennung, bei der einer Menge von handgeschriebenen Buchstaben die korrekten Buchstaben zugeordnet werden müssen. Aber auch in der Versicherungsbranche finden sich Anwendungen, wenn man die Menge der Versicherten in Gruppen ähnlichen Schadensverhaltens aufteilen will, um so die Prämien gerechter gestalten zu können. Auf diesem Gebiet wurde ein auf einem Sampling Ansatz basierender Algorithmus entwickelt, der für ein bestimmtes Abstandsmaß ein polynomielles Approximationsschema liefert und somit auf diesem Gebiet der erste Algorithmus überhaupt ist, der in akzeptabler Zeit eine Lösung mit garantierter Güte liefert.