A clustering is the partition of some set of objects into groups, the so-called clusters. Computing a good clustering is a well-known problem from machine learning and data mining, with applications is numerous areas, such as data compression, image and signal processing, and pattern recognition. One of the most important partitioning clustering problems is the K-Means problem. However, in practice it is not always sensible to uniquely assign each data point to a single cluster. In contrast, in a soft clustering, each data point belongs to each cluster with a certain degree of membership. A popular soft clustering problem is the Maximum Likelihood Estimation (MLE) problem for mixture models. The Expectation-Maximization (EM) algorithm, which is a generalization of Lloyd's algorithm for the K-Means problem, is a popular tool for solving such an MLE problem. However, a downside of this algorithm is that it is only a heuristic with two significant weaknesses. There are no approximation guarantees for solutions computed by the EM algorithm and there is no known upper bound on its runtime.