Next: Testmengen in der ganzzahligen
Up: Randomisierte Algorithmen
Previous: Smooth Sets
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.
Webmaster<www@zpr.uni-koeln.de>
1999-07-28