Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

Codes and Cryptography Bildinformationen anzeigen

Codes and Cryptography

Dr. Sascha Brauer


Fakultät für Elektrotechnik, Informatik und Mathematik > Institut für Informatik > Codes und Kryptographie


+49 5251 60-6627
Fürstenallee 11
33102 Paderborn

Liste im Research Information System öffnen


A Complexity Theoretical Study of Fuzzy K-Means

J. Blömer, S. Brauer, K. Bujna, ACM Transactions on Algorithms (2020), 16(4), pp. 1-25


How well do SEM algorithms imitate EM algorithms? A non-asymptotic analysis for mixture models

J. Blömer, S. Brauer, K. Bujna, D. Kuntze, Advances in Data Analysis and Classification (2020), 14, pp. 147–173



Complexity of single-swap heuristics for metric facility location and related problems

S. Brauer, Theoretical Computer Science (2019), 754, pp. 88-106



Coresets for Fuzzy K-Means with Applications

J. Blömer, S. Brauer, K. Bujna, in: 29th International Symposium on Algorithms and Computation (ISAAC 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018, pp. 46:1--46:12



Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems

S. Brauer, in: Lecture Notes in Computer Science, Springer International Publishing, 2017, pp. 116-127

Metric facility location and K-means are well-known problems of combinatorial optimization. Both admit a fairly simple heuristic called single-swap, which adds, drops or swaps open facilities until it reaches a local optimum. For both problems, it is known that this algorithm produces a solution that is at most a constant factor worse than the respective global optimum. In this paper, we show that single-swap applied to the weighted metric uncapacitated facility location and weighted discrete K-means problem is tightly PLS-complete and hence has exponential worst-case running time.


A Theoretical Analysis of the Fuzzy K-Means Problem

J. Blömer, S. Brauer, K. Bujna, in: 2016 IEEE 16th International Conference on Data Mining (ICDM), IEEE, 2016, pp. 805-810

One of the most popular fuzzy clustering techniques is the fuzzy K-means algorithm (also known as fuzzy-c-means or FCM algorithm). In contrast to the K-means and K-median problem, the underlying fuzzy K-means problem has not been studied from a theoretical point of view. In particular, there are no algorithms with approximation guarantees similar to the famous K-means++ algorithm known for the fuzzy K-means problem. This work initiates the study of the fuzzy K-means problem from an algorithmic and complexity theoretic perspective. We show that optimal solutions for the fuzzy K-means problem cannot, in general, be expressed by radicals over the input points. Surprisingly, this already holds for simple inputs in one-dimensional space. Hence, one cannot expect to compute optimal solutions exactly. We give the first (1+eps)-approximation algorithms for the fuzzy K-means problem. First, we present a deterministic approximation algorithm whose runtime is polynomial in N and linear in the dimension D of the input set, given that K is constant, i.e. a polynomial time approximation scheme (PTAS) for fixed K. We achieve this result by showing that for each soft clustering there exists a hard clustering with similar properties. Second, by using techniques known from coreset constructions for the K-means problem, we develop a deterministic approximation algorithm that runs in time almost linear in N but exponential in the dimension D. We complement these results with a randomized algorithm which imposes some natural restrictions on the sought solution and whose runtime is comparable to some of the most efficient approximation algorithms for K-means, i.e. linear in the number of points and the dimension, but exponential in the number of clusters.


Liste im Research Information System öffnen

Die Universität der Informationsgesellschaft