@article{20888,
author = {{Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}},
issn = {{1549-6325}},
journal = {{ACM Transactions on Algorithms}},
number = {{4}},
pages = {{1--25}},
title = {{{A Complexity Theoretical Study of Fuzzy K-Means}}},
doi = {{10.1145/3409385}},
volume = {{16}},
year = {{2020}},
}
@article{10790,
author = {{Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin and Kuntze, Daniel}},
issn = {{1862-5347}},
journal = {{Advances in Data Analysis and Classification}},
pages = {{147–173}},
title = {{{How well do SEM algorithms imitate EM algorithms? A non-asymptotic analysis for mixture models}}},
doi = {{10.1007/s11634-019-00366-7}},
volume = {{14}},
year = {{2020}},
}
@article{2916,
author = {{Brauer, Sascha}},
issn = {{0304-3975}},
journal = {{Theoretical Computer Science}},
pages = {{88--106}},
publisher = {{Elsevier}},
title = {{{Complexity of single-swap heuristics for metric facility location and related problems}}},
doi = {{10.1016/j.tcs.2018.04.048}},
volume = {{754}},
year = {{2019}},
}
@phdthesis{13679,
author = {{Brauer, Sascha}},
title = {{{Classification and Approximation of Geometric Location Problems}}},
doi = {{10.17619/UNIPB/1-816}},
year = {{2019}},
}
@inproceedings{4344,
author = {{Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}},
booktitle = {{29th International Symposium on Algorithms and Computation (ISAAC 2018)}},
isbn = {{978-3-95977-094-1}},
location = {{Jiaoxi, Yilan County, Taiwan}},
pages = {{46:1----46:12}},
publisher = {{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}},
title = {{{Coresets for Fuzzy K-Means with Applications}}},
doi = {{10.4230/LIPIcs.ISAAC.2018.46}},
year = {{2018}},
}
@inbook{2381,
abstract = {{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.}},
author = {{Brauer, Sascha}},
booktitle = {{Lecture Notes in Computer Science}},
editor = {{Fotakis, Dimitris and Pagourtzis, Aris and Paschos, Vangelis Th.}},
isbn = {{9783319575858}},
issn = {{0302-9743}},
location = {{Athens, Greece}},
pages = {{116--127}},
publisher = {{Springer International Publishing}},
title = {{{Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems}}},
doi = {{10.1007/978-3-319-57586-5_11}},
volume = {{10236}},
year = {{2017}},
}
@unpublished{2969,
author = {{Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}},
publisher = {{Computing Research Repository}},
title = {{{Hard-Clustering with Gaussian Mixture Models}}},
year = {{2016}},
}
@inproceedings{2367,
abstract = {{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.}},
author = {{Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}},
booktitle = {{2016 IEEE 16th International Conference on Data Mining (ICDM)}},
isbn = {{9781509054732}},
keywords = {{unsolvability by radicals, clustering, fuzzy k-means, probabilistic method, approximation algorithms, randomized algorithms}},
location = {{Barcelona, Spain}},
pages = {{805--810}},
publisher = {{IEEE}},
title = {{{A Theoretical Analysis of the Fuzzy K-Means Problem}}},
doi = {{10.1109/icdm.2016.0094}},
year = {{2016}},
}
@misc{2900,
author = {{Brauer, Sascha}},
title = {{{A Probabilistic Expectation Maximization Algorithm for Multivariate Laplacian Mixtures}}},
year = {{2014}},
}