TY - JOUR
AU - Blömer, Johannes
AU - Brauer, Sascha
AU - Bujna, Kathrin
ID - 20888
IS - 4
JF - ACM Transactions on Algorithms
SN - 1549-6325
TI - A Complexity Theoretical Study of Fuzzy K-Means
VL - 16
ER -
TY - JOUR
AU - Blömer, Johannes
AU - Brauer, Sascha
AU - Bujna, Kathrin
AU - Kuntze, Daniel
ID - 10790
JF - Advances in Data Analysis and Classification
SN - 1862-5347
TI - How well do SEM algorithms imitate EM algorithms? A non-asymptotic analysis for mixture models
VL - 14
ER -
TY - JOUR
AU - Brauer, Sascha
ID - 2916
JF - Theoretical Computer Science
SN - 0304-3975
TI - Complexity of single-swap heuristics for metric facility location and related problems
VL - 754
ER -
TY - THES
AU - Brauer, Sascha
ID - 13679
TI - Classification and Approximation of Geometric Location Problems
ER -
TY - CONF
AU - Blömer, Johannes
AU - Brauer, Sascha
AU - Bujna, Kathrin
ID - 4344
SN - 978-3-95977-094-1
T2 - 29th International Symposium on Algorithms and Computation (ISAAC 2018)
TI - Coresets for Fuzzy K-Means with Applications
ER -
TY - CHAP
AB - 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.
AU - Brauer, Sascha
ED - Fotakis, Dimitris
ED - Pagourtzis, Aris
ED - Paschos, Vangelis Th.
ID - 2381
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
VL - 10236
ER -
TY - GEN
AU - Blömer, Johannes
AU - Brauer, Sascha
AU - Bujna, Kathrin
ID - 2969
TI - Hard-Clustering with Gaussian Mixture Models
ER -
TY - CONF
AB - 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.
AU - Blömer, Johannes
AU - Brauer, Sascha
AU - Bujna, Kathrin
ID - 2367
KW - unsolvability by radicals
KW - clustering
KW - fuzzy k-means
KW - probabilistic method
KW - approximation algorithms
KW - randomized algorithms
SN - 9781509054732
T2 - 2016 IEEE 16th International Conference on Data Mining (ICDM)
TI - A Theoretical Analysis of the Fuzzy K-Means Problem
ER -
TY - GEN
AU - Brauer, Sascha
ID - 2900
TI - A Probabilistic Expectation Maximization Algorithm for Multivariate Laplacian Mixtures
ER -