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