[{"author":[{"first_name":"Johannes","last_name":"Blömer","full_name":"Blömer, Johannes","id":"23"},{"id":"13291","first_name":"Sascha","last_name":"Brauer","full_name":"Brauer, Sascha"},{"full_name":"Bujna, Kathrin","first_name":"Kathrin","last_name":"Bujna"}],"publication_identifier":{"issn":["1549-6325","1549-6333"]},"title":"A Complexity Theoretical Study of Fuzzy K-Means","year":"2020","intvolume":"        16","publication_status":"published","date_updated":"2022-01-06T06:54:41Z","language":[{"iso":"eng"}],"doi":"10.1145/3409385","issue":"4","publication":"ACM Transactions on Algorithms","date_created":"2021-01-08T08:51:42Z","department":[{"_id":"64"}],"type":"journal_article","status":"public","_id":"20888","page":"1-25","volume":16,"user_id":"13291","citation":{"short":"J. Blömer, S. Brauer, K. Bujna, ACM Transactions on Algorithms 16 (2020) 1–25.","chicago":"Blömer, Johannes, Sascha Brauer, and Kathrin Bujna. “A Complexity Theoretical Study of Fuzzy K-Means.” <i>ACM Transactions on Algorithms</i> 16, no. 4 (2020): 1–25. <a href=\"https://doi.org/10.1145/3409385\">https://doi.org/10.1145/3409385</a>.","ieee":"J. Blömer, S. Brauer, and K. Bujna, “A Complexity Theoretical Study of Fuzzy K-Means,” <i>ACM Transactions on Algorithms</i>, vol. 16, no. 4, pp. 1–25, 2020.","apa":"Blömer, J., Brauer, S., &#38; Bujna, K. (2020). A Complexity Theoretical Study of Fuzzy K-Means. <i>ACM Transactions on Algorithms</i>, <i>16</i>(4), 1–25. <a href=\"https://doi.org/10.1145/3409385\">https://doi.org/10.1145/3409385</a>","bibtex":"@article{Blömer_Brauer_Bujna_2020, title={A Complexity Theoretical Study of Fuzzy K-Means}, volume={16}, DOI={<a href=\"https://doi.org/10.1145/3409385\">10.1145/3409385</a>}, number={4}, journal={ACM Transactions on Algorithms}, author={Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}, year={2020}, pages={1–25} }","ama":"Blömer J, Brauer S, Bujna K. A Complexity Theoretical Study of Fuzzy K-Means. <i>ACM Transactions on Algorithms</i>. 2020;16(4):1-25. doi:<a href=\"https://doi.org/10.1145/3409385\">10.1145/3409385</a>","mla":"Blömer, Johannes, et al. “A Complexity Theoretical Study of Fuzzy K-Means.” <i>ACM Transactions on Algorithms</i>, vol. 16, no. 4, 2020, pp. 1–25, doi:<a href=\"https://doi.org/10.1145/3409385\">10.1145/3409385</a>."},"project":[{"_id":"45","name":"Soft-Clustering - Von Heuristiken zu Approximationsalgorithmen"}]},{"volume":14,"user_id":"13291","doi":"10.1007/s11634-019-00366-7","language":[{"iso":"eng"}],"_id":"10790","page":"147–173","intvolume":"        14","publication_status":"published","date_updated":"2022-01-06T06:50:50Z","publication_identifier":{"issn":["1862-5347","1862-5355"]},"author":[{"first_name":"Johannes","last_name":"Blömer","full_name":"Blömer, Johannes","id":"23"},{"full_name":"Brauer, Sascha","last_name":"Brauer","first_name":"Sascha","id":"13291"},{"last_name":"Bujna","first_name":"Kathrin","full_name":"Bujna, Kathrin"},{"full_name":"Kuntze, Daniel","first_name":"Daniel","last_name":"Kuntze"}],"status":"public","year":"2020","title":"How well do SEM algorithms imitate EM algorithms? A non-asymptotic analysis for mixture models","department":[{"_id":"64"}],"type":"journal_article","date_created":"2019-07-11T08:08:25Z","project":[{"name":"Soft-Clustering - Von Heuristiken zu Approximationsalgorithmen","_id":"45"}],"citation":{"short":"J. Blömer, S. Brauer, K. Bujna, D. Kuntze, Advances in Data Analysis and Classification 14 (2020) 147–173.","chicago":"Blömer, Johannes, Sascha Brauer, Kathrin Bujna, and Daniel Kuntze. “How Well Do SEM Algorithms Imitate EM Algorithms? A Non-Asymptotic Analysis for Mixture Models.” <i>Advances in Data Analysis and Classification</i> 14 (2020): 147–173. <a href=\"https://doi.org/10.1007/s11634-019-00366-7\">https://doi.org/10.1007/s11634-019-00366-7</a>.","ieee":"J. Blömer, S. Brauer, K. Bujna, and D. Kuntze, “How well do SEM algorithms imitate EM algorithms? A non-asymptotic analysis for mixture models,” <i>Advances in Data Analysis and Classification</i>, vol. 14, pp. 147–173, 2020.","apa":"Blömer, J., Brauer, S., Bujna, K., &#38; Kuntze, D. (2020). How well do SEM algorithms imitate EM algorithms? A non-asymptotic analysis for mixture models. <i>Advances in Data Analysis and Classification</i>, <i>14</i>, 147–173. <a href=\"https://doi.org/10.1007/s11634-019-00366-7\">https://doi.org/10.1007/s11634-019-00366-7</a>","bibtex":"@article{Blömer_Brauer_Bujna_Kuntze_2020, title={How well do SEM algorithms imitate EM algorithms? A non-asymptotic analysis for mixture models}, volume={14}, DOI={<a href=\"https://doi.org/10.1007/s11634-019-00366-7\">10.1007/s11634-019-00366-7</a>}, journal={Advances in Data Analysis and Classification}, author={Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin and Kuntze, Daniel}, year={2020}, pages={147–173} }","ama":"Blömer J, Brauer S, Bujna K, Kuntze D. How well do SEM algorithms imitate EM algorithms? A non-asymptotic analysis for mixture models. <i>Advances in Data Analysis and Classification</i>. 2020;14:147–173. doi:<a href=\"https://doi.org/10.1007/s11634-019-00366-7\">10.1007/s11634-019-00366-7</a>","mla":"Blömer, Johannes, et al. “How Well Do SEM Algorithms Imitate EM Algorithms? A Non-Asymptotic Analysis for Mixture Models.” <i>Advances in Data Analysis and Classification</i>, vol. 14, 2020, pp. 147–173, doi:<a href=\"https://doi.org/10.1007/s11634-019-00366-7\">10.1007/s11634-019-00366-7</a>."},"publication":"Advances in Data Analysis and Classification"},{"date_updated":"2022-01-06T06:58:46Z","publication_status":"published","intvolume":"       754","year":"2019","title":"Complexity of single-swap heuristics for metric facility location and related problems","publication_identifier":{"issn":["0304-3975"]},"author":[{"id":"13291","full_name":"Brauer, Sascha","first_name":"Sascha","last_name":"Brauer"}],"doi":"10.1016/j.tcs.2018.04.048","language":[{"iso":"eng"}],"publication":"Theoretical Computer Science","type":"journal_article","department":[{"_id":"64"}],"date_created":"2018-05-25T11:10:36Z","status":"public","user_id":"13291","volume":754,"page":"88-106","publisher":"Elsevier","_id":"2916","project":[{"_id":"45","name":"Soft-Clustering - Von Heuristiken zu Approximationsalgorithmen"}],"citation":{"mla":"Brauer, Sascha. “Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems.” <i>Theoretical Computer Science</i>, vol. 754, Elsevier, 2019, pp. 88–106, doi:<a href=\"https://doi.org/10.1016/j.tcs.2018.04.048\">10.1016/j.tcs.2018.04.048</a>.","bibtex":"@article{Brauer_2019, title={Complexity of single-swap heuristics for metric facility location and related problems}, volume={754}, DOI={<a href=\"https://doi.org/10.1016/j.tcs.2018.04.048\">10.1016/j.tcs.2018.04.048</a>}, journal={Theoretical Computer Science}, publisher={Elsevier}, author={Brauer, Sascha}, year={2019}, pages={88–106} }","ama":"Brauer S. Complexity of single-swap heuristics for metric facility location and related problems. <i>Theoretical Computer Science</i>. 2019;754:88-106. doi:<a href=\"https://doi.org/10.1016/j.tcs.2018.04.048\">10.1016/j.tcs.2018.04.048</a>","ieee":"S. Brauer, “Complexity of single-swap heuristics for metric facility location and related problems,” <i>Theoretical Computer Science</i>, vol. 754, pp. 88–106, 2019.","apa":"Brauer, S. (2019). Complexity of single-swap heuristics for metric facility location and related problems. <i>Theoretical Computer Science</i>, <i>754</i>, 88–106. <a href=\"https://doi.org/10.1016/j.tcs.2018.04.048\">https://doi.org/10.1016/j.tcs.2018.04.048</a>","chicago":"Brauer, Sascha. “Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems.” <i>Theoretical Computer Science</i> 754 (2019): 88–106. <a href=\"https://doi.org/10.1016/j.tcs.2018.04.048\">https://doi.org/10.1016/j.tcs.2018.04.048</a>.","short":"S. Brauer, Theoretical Computer Science 754 (2019) 88–106."}},{"_id":"13679","language":[{"iso":"eng"}],"user_id":"13291","doi":"10.17619/UNIPB/1-816","title":"Classification and Approximation of Geometric Location Problems","year":"2019","status":"public","author":[{"full_name":"Brauer, Sascha","first_name":"Sascha","last_name":"Brauer","id":"13291"}],"date_updated":"2022-01-06T06:51:41Z","date_created":"2019-10-09T10:00:53Z","place":"Paderborn","type":"dissertation","department":[{"_id":"64"}],"citation":{"ieee":"S. Brauer, <i>Classification and Approximation of Geometric Location Problems</i>. Paderborn, 2019.","mla":"Brauer, Sascha. <i>Classification and Approximation of Geometric Location Problems</i>. 2019, doi:<a href=\"https://doi.org/10.17619/UNIPB/1-816\">10.17619/UNIPB/1-816</a>.","apa":"Brauer, S. (2019). <i>Classification and Approximation of Geometric Location Problems</i>. Paderborn. <a href=\"https://doi.org/10.17619/UNIPB/1-816\">https://doi.org/10.17619/UNIPB/1-816</a>","bibtex":"@book{Brauer_2019, place={Paderborn}, title={Classification and Approximation of Geometric Location Problems}, DOI={<a href=\"https://doi.org/10.17619/UNIPB/1-816\">10.17619/UNIPB/1-816</a>}, author={Brauer, Sascha}, year={2019} }","ama":"Brauer S. <i>Classification and Approximation of Geometric Location Problems</i>. Paderborn; 2019. doi:<a href=\"https://doi.org/10.17619/UNIPB/1-816\">10.17619/UNIPB/1-816</a>","short":"S. Brauer, Classification and Approximation of Geometric Location Problems, Paderborn, 2019.","chicago":"Brauer, Sascha. <i>Classification and Approximation of Geometric Location Problems</i>. Paderborn, 2019. <a href=\"https://doi.org/10.17619/UNIPB/1-816\">https://doi.org/10.17619/UNIPB/1-816</a>."},"supervisor":[{"id":"23","first_name":"Johannes","last_name":"Blömer","full_name":"Blömer, Johannes"}],"project":[{"name":"Soft-Clustering - Von Heuristiken zu Approximationsalgorithmen","_id":"45"}]},{"project":[{"_id":"45","name":"Soft-Clustering - Von Heuristiken zu Approximationsalgorithmen"}],"publication":"29th International Symposium on Algorithms and Computation  (ISAAC 2018)","citation":{"bibtex":"@inproceedings{Blömer_Brauer_Bujna_2018, title={Coresets for Fuzzy K-Means with Applications}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.ISAAC.2018.46\">10.4230/LIPIcs.ISAAC.2018.46</a>}, booktitle={29th International Symposium on Algorithms and Computation  (ISAAC 2018)}, publisher={Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, author={Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}, year={2018}, pages={46:1--46:12} }","ama":"Blömer J, Brauer S, Bujna K. Coresets for Fuzzy K-Means with Applications. In: <i>29th International Symposium on Algorithms and Computation  (ISAAC 2018)</i>. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik; 2018:46:1--46:12. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ISAAC.2018.46\">10.4230/LIPIcs.ISAAC.2018.46</a>","mla":"Blömer, Johannes, et al. “Coresets for Fuzzy K-Means with Applications.” <i>29th International Symposium on Algorithms and Computation  (ISAAC 2018)</i>, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018, pp. 46:1--46:12, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ISAAC.2018.46\">10.4230/LIPIcs.ISAAC.2018.46</a>.","chicago":"Blömer, Johannes, Sascha Brauer, and Kathrin Bujna. “Coresets for Fuzzy K-Means with Applications.” In <i>29th International Symposium on Algorithms and Computation  (ISAAC 2018)</i>, 46:1--46:12. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.ISAAC.2018.46\">https://doi.org/10.4230/LIPIcs.ISAAC.2018.46</a>.","short":"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.","ieee":"J. Blömer, S. Brauer, and K. Bujna, “Coresets for Fuzzy K-Means with Applications,” in <i>29th International Symposium on Algorithms and Computation  (ISAAC 2018)</i>, Jiaoxi, Yilan County, Taiwan, 2018, pp. 46:1--46:12.","apa":"Blömer, J., Brauer, S., &#38; Bujna, K. (2018). Coresets for Fuzzy K-Means with Applications. In <i>29th International Symposium on Algorithms and Computation  (ISAAC 2018)</i> (pp. 46:1--46:12). Jiaoxi, Yilan County, Taiwan: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ISAAC.2018.46\">https://doi.org/10.4230/LIPIcs.ISAAC.2018.46</a>"},"type":"conference","department":[{"_id":"64"}],"date_created":"2018-09-03T08:04:19Z","publication_status":"published","date_updated":"2022-01-06T07:00:57Z","status":"public","year":"2018","title":"Coresets for Fuzzy K-Means with Applications","author":[{"full_name":"Blömer, Johannes","last_name":"Blömer","first_name":"Johannes","id":"23"},{"full_name":"Brauer, Sascha","last_name":"Brauer","first_name":"Sascha","id":"13291"},{"full_name":"Bujna, Kathrin","last_name":"Bujna","first_name":"Kathrin"}],"publication_identifier":{"isbn":["978-3-95977-094-1"]},"conference":{"name":"29th International Symposium on Algorithms and Computation (ISAAC)","start_date":"2018-12-17","location":"Jiaoxi, Yilan County, Taiwan","end_date":"2018-12-19"},"user_id":"13291","doi":"10.4230/LIPIcs.ISAAC.2018.46","page":"46:1--46:12","publisher":"Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik","_id":"4344","language":[{"iso":"eng"}]},{"conference":{"start_date":"2017-05-24","name":"10th International Conference on Algorithms and Complexity","location":"Athens, Greece","end_date":"2017-05-26"},"status":"public","editor":[{"full_name":"Fotakis, Dimitris","first_name":"Dimitris","last_name":"Fotakis"},{"full_name":"Pagourtzis, Aris","last_name":"Pagourtzis","first_name":"Aris"},{"first_name":"Vangelis Th.","last_name":"Paschos","full_name":"Paschos, Vangelis Th."}],"volume":10236,"user_id":"13291","_id":"2381","publisher":"Springer International Publishing","page":"116-127","citation":{"ieee":"S. Brauer, “Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems,” in <i>Lecture Notes in Computer Science</i>, vol. 10236, D. Fotakis, A. Pagourtzis, and V. T. Paschos, Eds. Cham: Springer International Publishing, 2017, pp. 116–127.","apa":"Brauer, S. (2017). Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems. In D. Fotakis, A. Pagourtzis, &#38; V. T. Paschos (Eds.), <i>Lecture Notes in Computer Science</i> (Vol. 10236, pp. 116–127). Cham: Springer International Publishing. <a href=\"https://doi.org/10.1007/978-3-319-57586-5_11\">https://doi.org/10.1007/978-3-319-57586-5_11</a>","chicago":"Brauer, Sascha. “Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems.” In <i>Lecture Notes in Computer Science</i>, edited by Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, 10236:116–27. Cham: Springer International Publishing, 2017. <a href=\"https://doi.org/10.1007/978-3-319-57586-5_11\">https://doi.org/10.1007/978-3-319-57586-5_11</a>.","short":"S. Brauer, in: D. Fotakis, A. Pagourtzis, V.T. Paschos (Eds.), Lecture Notes in Computer Science, Springer International Publishing, Cham, 2017, pp. 116–127.","mla":"Brauer, Sascha. “Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems.” <i>Lecture Notes in Computer Science</i>, edited by Dimitris Fotakis et al., vol. 10236, Springer International Publishing, 2017, pp. 116–27, doi:<a href=\"https://doi.org/10.1007/978-3-319-57586-5_11\">10.1007/978-3-319-57586-5_11</a>.","bibtex":"@inbook{Brauer_2017, place={Cham}, title={Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems}, volume={10236}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-57586-5_11\">10.1007/978-3-319-57586-5_11</a>}, booktitle={Lecture Notes in Computer Science}, publisher={Springer International Publishing}, author={Brauer, Sascha}, editor={Fotakis, Dimitris and Pagourtzis, Aris and Paschos, Vangelis Th.Editors}, year={2017}, pages={116–127} }","ama":"Brauer S. Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems. In: Fotakis D, Pagourtzis A, Paschos VT, eds. <i>Lecture Notes in Computer Science</i>. Vol 10236. Cham: Springer International Publishing; 2017:116-127. doi:<a href=\"https://doi.org/10.1007/978-3-319-57586-5_11\">10.1007/978-3-319-57586-5_11</a>"},"place":"Cham","intvolume":"     10236","date_updated":"2022-01-06T06:56:00Z","publication_status":"published","publication_identifier":{"isbn":["9783319575858","9783319575865"],"issn":["0302-9743","1611-3349"]},"author":[{"first_name":"Sascha","last_name":"Brauer","full_name":"Brauer, Sascha","id":"13291"}],"year":"2017","title":"Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems","doi":"10.1007/978-3-319-57586-5_11","language":[{"iso":"eng"}],"abstract":[{"text":"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.","lang":"eng"}],"publication":"Lecture Notes in Computer Science","department":[{"_id":"64"}],"type":"book_chapter","date_created":"2018-04-17T12:20:53Z"},{"date_created":"2018-06-04T12:26:51Z","type":"preprint","department":[{"_id":"64"}],"oa":"1","citation":{"mla":"Blömer, Johannes, et al. <i>Hard-Clustering with Gaussian Mixture Models</i>. Computing Research Repository, 2016.","ama":"Blömer J, Brauer S, Bujna K. Hard-Clustering with Gaussian Mixture Models. 2016.","bibtex":"@article{Blömer_Brauer_Bujna_2016, title={Hard-Clustering with Gaussian Mixture Models}, publisher={Computing Research Repository}, author={Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}, year={2016} }","apa":"Blömer, J., Brauer, S., &#38; Bujna, K. (2016). Hard-Clustering with Gaussian Mixture Models. Computing Research Repository.","ieee":"J. Blömer, S. Brauer, and K. Bujna, “Hard-Clustering with Gaussian Mixture Models.” Computing Research Repository, 2016.","short":"J. Blömer, S. Brauer, K. Bujna, (2016).","chicago":"Blömer, Johannes, Sascha Brauer, and Kathrin Bujna. “Hard-Clustering with Gaussian Mixture Models.” Computing Research Repository, 2016."},"main_file_link":[{"url":"https://arxiv.org/abs/1603.06478","open_access":"1"}],"_id":"2969","publisher":"Computing Research Repository","user_id":"25078","year":"2016","status":"public","title":"Hard-Clustering with Gaussian Mixture Models","author":[{"id":"23","last_name":"Blömer","first_name":"Johannes","full_name":"Blömer, Johannes"},{"id":"13291","first_name":"Sascha","last_name":"Brauer","full_name":"Brauer, Sascha"},{"full_name":"Bujna, Kathrin","last_name":"Bujna","first_name":"Kathrin"}],"date_updated":"2022-01-06T06:58:49Z"},{"citation":{"ama":"Blömer J, Brauer S, Bujna K. A Theoretical Analysis of the Fuzzy K-Means Problem. In: <i>2016 IEEE 16th International Conference on Data Mining (ICDM)</i>. IEEE; 2016:805-810. doi:<a href=\"https://doi.org/10.1109/icdm.2016.0094\">10.1109/icdm.2016.0094</a>","bibtex":"@inproceedings{Blömer_Brauer_Bujna_2016, title={A Theoretical Analysis of the Fuzzy K-Means Problem}, DOI={<a href=\"https://doi.org/10.1109/icdm.2016.0094\">10.1109/icdm.2016.0094</a>}, booktitle={2016 IEEE 16th International Conference on Data Mining (ICDM)}, publisher={IEEE}, author={Blömer, Johannes and Brauer, Sascha and Bujna, Kathrin}, year={2016}, pages={805–810} }","mla":"Blömer, Johannes, et al. “A Theoretical Analysis of the Fuzzy K-Means Problem.” <i>2016 IEEE 16th International Conference on Data Mining (ICDM)</i>, IEEE, 2016, pp. 805–10, doi:<a href=\"https://doi.org/10.1109/icdm.2016.0094\">10.1109/icdm.2016.0094</a>.","short":"J. Blömer, S. Brauer, K. Bujna, in: 2016 IEEE 16th International Conference on Data Mining (ICDM), IEEE, 2016, pp. 805–810.","chicago":"Blömer, Johannes, Sascha Brauer, and Kathrin Bujna. “A Theoretical Analysis of the Fuzzy K-Means Problem.” In <i>2016 IEEE 16th International Conference on Data Mining (ICDM)</i>, 805–10. IEEE, 2016. <a href=\"https://doi.org/10.1109/icdm.2016.0094\">https://doi.org/10.1109/icdm.2016.0094</a>.","apa":"Blömer, J., Brauer, S., &#38; Bujna, K. (2016). A Theoretical Analysis of the Fuzzy K-Means Problem. In <i>2016 IEEE 16th International Conference on Data Mining (ICDM)</i> (pp. 805–810). Barcelona, Spain: IEEE. <a href=\"https://doi.org/10.1109/icdm.2016.0094\">https://doi.org/10.1109/icdm.2016.0094</a>","ieee":"J. Blömer, S. Brauer, and K. Bujna, “A Theoretical Analysis of the Fuzzy K-Means Problem,” in <i>2016 IEEE 16th International Conference on Data Mining (ICDM)</i>, Barcelona, Spain, 2016, pp. 805–810."},"conference":{"start_date":"2016-12-12","name":"IEEE 16th International Conference on Data Mining (ICDM)","location":"Barcelona, Spain","end_date":"2016-12-15"},"status":"public","_id":"2367","publisher":"IEEE","page":"805-810","user_id":"25078","publication":"2016 IEEE 16th International Conference on Data Mining (ICDM)","abstract":[{"lang":"eng","text":"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."}],"date_created":"2018-04-17T11:46:07Z","department":[{"_id":"64"}],"keyword":["unsolvability by radicals","clustering","fuzzy k-means","probabilistic method","approximation algorithms","randomized algorithms"],"type":"conference","author":[{"first_name":"Johannes","last_name":"Blömer","full_name":"Blömer, Johannes","id":"23"},{"id":"13291","last_name":"Brauer","first_name":"Sascha","full_name":"Brauer, Sascha"},{"first_name":"Kathrin","last_name":"Bujna","full_name":"Bujna, Kathrin"}],"publication_identifier":{"isbn":["9781509054732"]},"year":"2016","title":"A Theoretical Analysis of the Fuzzy K-Means Problem","publication_status":"published","date_updated":"2022-01-06T06:55:58Z","language":[{"iso":"eng"}],"doi":"10.1109/icdm.2016.0094"},{"_id":"2900","user_id":"25078","ddc":["000"],"title":"A Probabilistic Expectation Maximization Algorithm for Multivariate Laplacian Mixtures","status":"public","year":"2014","author":[{"full_name":"Brauer, Sascha","last_name":"Brauer","first_name":"Sascha","id":"13291"}],"date_updated":"2022-01-06T06:58:44Z","has_accepted_license":"1","file":[{"creator":"feidens","date_created":"2018-05-25T09:45:33Z","relation":"main_file","date_updated":"2018-05-25T09:45:33Z","file_name":"2014_Brauer_AProbabilisticExpectationMaximizationAlgorithmForMultivariateLaplacianMixtures.pdf","file_size":971935,"access_level":"closed","file_id":"2901","success":1,"content_type":"application/pdf"}],"date_created":"2018-05-25T09:45:38Z","type":"mastersthesis","department":[{"_id":"64"}],"file_date_updated":"2018-05-25T09:45:33Z","citation":{"apa":"Brauer, S. (2014). <i>A Probabilistic Expectation Maximization Algorithm for Multivariate Laplacian Mixtures</i>.","ieee":"S. Brauer, <i>A Probabilistic Expectation Maximization Algorithm for Multivariate Laplacian Mixtures</i>. 2014.","short":"S. Brauer, A Probabilistic Expectation Maximization Algorithm for Multivariate Laplacian Mixtures, 2014.","chicago":"Brauer, Sascha. <i>A Probabilistic Expectation Maximization Algorithm for Multivariate Laplacian Mixtures</i>, 2014.","mla":"Brauer, Sascha. <i>A Probabilistic Expectation Maximization Algorithm for Multivariate Laplacian Mixtures</i>. 2014.","ama":"Brauer S. <i>A Probabilistic Expectation Maximization Algorithm for Multivariate Laplacian Mixtures</i>.; 2014.","bibtex":"@book{Brauer_2014, title={A Probabilistic Expectation Maximization Algorithm for Multivariate Laplacian Mixtures}, author={Brauer, Sascha}, year={2014} }"},"supervisor":[{"full_name":"Blömer, Johannes","last_name":"Blömer","first_name":"Johannes","id":"23"}]}]