Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, January 22, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Julian Lorenz
In this talk I will present my diploma thesis on "geometric clustering problems". We will consider two different models, namely k-Clustering and minsum-Clustering. Given n points in R^d, in k-clustering the problem is to find k clusters such that the sum of squared distances of each data point to the center of its cluster is minimized. We will focus on the case when the dimension d is part of the input, and use a dimension reduction technique by Johnson-Lindenstrauss to improve known algorithms. In minsum-clustering the problem is to minimize the sum of all distances between points in the same cluster. I will present an approximation approach by iterative matchings, and give some partial results about its approximation behaviour.
Automatic MiSe System Software Version 1.4803M | admin login