Open Theses
In addition to the topics listed here, we can also find topics adapted to your own interests at short notice upon request. For an orientation on what you might be interested in, we recommend to have a look at the main research topics of the working group.
If you are interested in writing a thesis with us, please contact Prof. Blömer. Even if none of the listed topics below interests you, still feel free to contact us and we'll try to find a good topic together. If you are looking for a general overview of open topics including other working groups, then please see this overview.
Master's theses
Fuzzy k-Means is a popular generalization of the classical k-Means problem to soft clusterings. From an algorithmic perspective however, it is much more difficult to compute provably good solutions. Typically, these problems use the squared Euclidean distance to measure how far data points are apart. The squared Euclidean distance is part of the mu-similar Bregman divergences, a large class of dissimilarity measures sharing desirable characteristics.
Using sampling techniques to find good approximations of optimal centroids has proven to work for both, the k-Means problem using mu-similar Bregman divergences and also for the Fuzzy k-Means problem using the squared Euclidean distance. The goal of this thesis is to explore whether this can actually be combined to obtain a good approximation algorithm for the Fuzzy k-Means problem using mu-similar Bregman divergences.