{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T06:34:28Z","timestamp":1776148468103,"version":"3.50.1"},"publisher-location":"Cham","reference-count":48,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030394783","type":"print"},{"value":"9783030394790","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-39479-0_16","type":"book-chapter","created":{"date-parts":[[2020,1,24]],"date-time":"2020-01-24T20:03:47Z","timestamp":1579896227000},"page":"232-251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["Fair Coresets and Streaming Algorithms for Fair k-means"],"prefix":"10.1007","author":[{"given":"Melanie","family":"Schmidt","sequence":"first","affiliation":[]},{"given":"Chris","family":"Schwiegelshohn","sequence":"additional","affiliation":[]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,25]]},"reference":[{"key":"16_CR1","unstructured":"Awasthi, P., Charikar, M., Krishnaswamy, R., Sinop, A.K.: The hardness of approximation of Euclidean k-means. In: 31st International Symposium on Computational Geometry (SoCG), pp. 754\u2013767 (2015)"},{"key":"16_CR2","unstructured":"Ailon, N., Jaiswal, R., Monteleoni, C.: Streaming k-means approximation. In: Proceedings of the 22nd Neural Information Processing Systems (NIPS), pp. 10\u201318 (2009)"},{"key":"16_CR3","unstructured":"Angwin, J., Larson, J., Mattu, S., Kirchner, L.: Machine bias: there\u2019s software used across the country to predict future criminals and it\u2019s biased against blacks. ProPublica, May 2016"},{"key":"16_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2133803.2184450","volume":"17","author":"MR Ackermann","year":"2012","unstructured":"Ackermann, M.R., M\u00e4rtens, M., Raupach, C., Swierkot, K., Lammersen, C., Sohler, C.: StreamKM++: a clustering algorithm for data streams. ACM J. Exper. Algorithmics 17, 1\u201330 (2012). Article no. 2.4","journal-title":"ACM J. Exper. Algorithmics"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Ahmadian, S., Norouzi-Fard, A., Svensson, O., Ward, J.: Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 61\u201372 (2017)","DOI":"10.1109\/FOCS.2017.15"},{"key":"16_CR6","unstructured":"Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1027\u20131035 (2007)"},{"key":"16_CR7","unstructured":"Braverman, V., Feldman, D., Lang, H.: New frameworks for offline and streaming coreset constructions, arXiv preprint arXiv:1612.00889 (2016)"},{"key":"16_CR8","unstructured":"Bercea, I.O., et al.: On the cost of essentially fair clusterings, CoRR abs\/1811.10319 (2018)"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Berk, R., Heidari, H., Jabbari, S., Kearns, M., Roth, A.: Fairness in criminal justice risk assessments: the state of the art, arXiv:1703.09207 (2017)","DOI":"10.1177\/0049124118782533"},{"key":"16_CR10","unstructured":"Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., Wagner, T.: Scalable fair clustering, CoRR abs\/1902.03519 (2019)"},{"issue":"1","key":"16_CR11","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00224-017-9820-7","volume":"62","author":"A Bhattacharya","year":"2018","unstructured":"Bhattacharya, A., Jaiswal, R., Kumar, A.: Faster algorithms for the constrained k-means problem. Theory Comput. Syst. 62(1), 93\u2013115 (2018)","journal-title":"Theory Comput. Syst."},{"key":"16_CR12","unstructured":"Boutsidis, C., Zouzias, A., Drineas, P.: Random projections for $$k$$ -means clustering.. In: Proceedings of the 24th Neural Information Processing Systems (NIPS), pp. 298\u2013306 (2010)"},{"issue":"2","key":"16_CR13","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1109\/TIT.2014.2375327","volume":"61","author":"C Boutsidis","year":"2015","unstructured":"Boutsidis, C., Zouzias, A., Mahoney, M.W., Drineas, P.: Randomized dimensionality reduction for k-means clustering. IEEE Trans. Inf. Theory 61(2), 1045\u20131062 (2015)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Cohen, M.B., Elder, S., Musco, C., Musco, C., Persu, M.: Dimensionality reduction for k-means clustering and low rank approximation. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), pp. 163\u2013172 (2015)","DOI":"10.1145\/2746539.2746569"},{"key":"16_CR15","unstructured":"Chouldechova, A.: Fair prediction with disparate impact: a study of bias in recidivism prediction instruments, arXiv: 1510.07524v1 (2016)"},{"key":"16_CR16","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. In: Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS), pp. 5036\u20135044 (2017)"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., Klein, P.N., Mathieu, C.: Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics. In: IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 353\u2013364 (2016)","DOI":"10.1109\/FOCS.2016.46"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Corbett-Davies, S., Pierson, E., Feller, A., Goel, S., Huq, A.: Algorithmic decision making and the cost of fairness. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 797\u2013806 (2017)","DOI":"10.1145\/3097983.3098095"},{"issue":"1\u20133","key":"16_CR19","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1023\/B:MACH.0000033113.59016.96","volume":"56","author":"P Drineas","year":"2004","unstructured":"Drineas, P., Frieze, A.M., Kannan, R., Vempala, S., Vinay, V.: Clustering large graphs via the singular value decomposition. Mach. Learn. 56(1\u20133), 9\u201333 (2004)","journal-title":"Mach. Learn."},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"Dwork, C., Hardt, M., Pitassi, T., Reingold, O., Zemel, R.: Fairness through awareness. In: ITCS 2012, pp. 214\u2013226 (2012)","DOI":"10.1145\/2090236.2090255"},{"key":"16_CR21","unstructured":"Ding, H., Xu, J.: A unified framework for clustering constrained data without locality property. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, 4\u20136 January 2015, pp. 1471\u20131490 (2015)"},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Feldman, M., Friedler, S.A., Moeller, J., Scheidegger, C., Venkatasubramanian, S.: Certifying and removing disparate impact. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 259\u2013268 (2015)","DOI":"10.1145\/2783258.2783311"},{"key":"16_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-3-642-40450-4_41","volume-title":"Algorithms ESA \u2013 2013","author":"H Fichtenberger","year":"2013","unstructured":"Fichtenberger, H., Gill\u00e9, M., Schmidt, M., Schwiegelshohn, C., Sohler, C.: BICO: BIRCH meets coresets for k-means clustering. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 481\u2013492. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40450-4_41"},{"key":"16_CR24","doi-asserted-by":"crossref","unstructured":"Feldman, D., Langberg, M.: A unified framework for approximating and clustering data. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pp. 569\u2013578 (2011)","DOI":"10.1145\/1993636.1993712"},{"key":"16_CR25","doi-asserted-by":"crossref","unstructured":"Feldman, D., Monemizadeh, M., Sohler, C.: A PTAS for k-means clustering based on weak coresets. In: Proceedings of the 23rd Symposium on Computational Geometry, pp. 11\u201318 (2007)","DOI":"10.1145\/1247069.1247072"},{"key":"16_CR26","doi-asserted-by":"crossref","unstructured":"Friggstad, Z., Rezapour, M., Salavatipour, M.R.: Local search yields a PTAS for k-means in doubling metrics. In: IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 365\u2013374 (2016)","DOI":"10.1109\/FOCS.2016.47"},{"key":"16_CR27","doi-asserted-by":"crossref","unstructured":"Frahling, G., Sohler, C.: Coresets in dynamic geometric data streams. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 209\u2013217 (2005)","DOI":"10.1145\/1060590.1060622"},{"key":"16_CR28","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1142\/S0218195908002787","volume":"18","author":"G Frahling","year":"2008","unstructured":"Frahling, G., Sohler, C.: A fast k-means implementation using coresets. Int. J. Comput. Geom. Appl. 18, 605\u2013625 (2008)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Feldman, D., Schmidt, M., Sohler, C.: Turning big data into tiny data: constant-size coresets for k-means, PCA and projective clustering. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1434\u20131453 (2013)","DOI":"10.1137\/1.9781611973105.103"},{"key":"16_CR30","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"16_CR31","unstructured":"Hardt, M., Price, E., Srebro, N.: Equality of opportunity in supervised learning. In: Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS) (2016)"},{"key":"16_CR32","doi-asserted-by":"crossref","unstructured":"Inaba, M., Katoh, N., Imai, H.: Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering (extended abstract). In: Proceedings of the Tenth Annual Symposium on Computational Geometry (SoCG), pp. 332\u2013339 (1994)","DOI":"10.1145\/177424.178042"},{"key":"16_CR33","doi-asserted-by":"crossref","unstructured":"Indyk, P., Mahabadi, S., Mahdian, M., Mirrokni, V.S.: Composable core-sets for diversity and coverage maximization. In: Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pp. 100\u2013108 (2014)","DOI":"10.1145\/2594538.2594560"},{"key":"16_CR34","unstructured":"Kleindessner, M., Awasthi, P., Morgenstern, J.: Fair k-center clustering for data summarization, CoRR abs\/1901.08628 (2019)"},{"issue":"7","key":"16_CR35","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1109\/TPAMI.2002.1017616","volume":"24","author":"T Kanungo","year":"2002","unstructured":"Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: An efficient k-means clustering algorithm: analysis and implementation. IEEE Trans. Pattern Anal. Mach. Intell. 24(7), 881\u2013892 (2002)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"16_CR36","unstructured":"Kleinberg, J.M., Mullainathan, S., Raghavan, M.: Inherent trade-offs in the fair determination of risk scores. In: 8th Innovations in Theoretical Computer Science Conference (ITCS), pp. 43:1\u201343:23 (2017)"},{"issue":"2","key":"16_CR37","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/1667053.1667054","volume":"57","author":"A Kumar","year":"2010","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM 57(2), 51\u2013532 (2010)","journal-title":"J. ACM"},{"key":"16_CR38","unstructured":"Lloyd, S.P.: Least squares quantization in PCM. Bell Laboratories Technical Memorandum (1957). Later published as [Llo82]"},{"issue":"2","key":"16_CR39","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"SP Lloyd","year":"1982","unstructured":"Lloyd, S.P.: Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129\u2013137 (1982)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"16_CR40","doi-asserted-by":"crossref","unstructured":"Langberg, M., Schulman, L.J.: Universal epsilon-approximators for integrals. In: Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 598\u2013607 (2010)","DOI":"10.1137\/1.9781611973075.50"},{"key":"16_CR41","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.ipl.2016.11.009","volume":"120","author":"E Lee","year":"2017","unstructured":"Lee, E., Schmidt, M., Wright, J.: Improved and simplified inapproximability for k-means. Inf. Process. Lett. 120, 40\u201343 (2017)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"16_CR42","first-page":"37","volume":"32","author":"A Munteanu","year":"2018","unstructured":"Munteanu, A., Schwiegelshohn, C.: Coresets-methods and history: a theoreticians design pattern for approximation and streaming algorithms. KI 32(1), 37\u201353 (2018)","journal-title":"KI"},{"key":"16_CR43","unstructured":"Munoz, C., Smith, M., Patil, D.: Big data: a report on algorithmic systems, opportunity, and civil rights. Executive Office of the President. The White House (2016)"},{"key":"16_CR44","unstructured":"R\u00f6sner, C., Schmidt, M.: Privacy preserving clustering with constraints. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP) (2018)"},{"key":"16_CR45","unstructured":"Schmidt, M.: Coresets and streaming algorithms for the k-means problem and related clustering objectives. Ph. D. thesis, Universit\u00e4t Dortmund (2014)"},{"key":"16_CR46","unstructured":"Schmidt, M., Schwiegelshohn, C., Sohler, C.: Fair coresets and streaming algorithms for fair k-means clustering, CoRR abs\/1812.10854 (2018)"},{"key":"16_CR47","unstructured":"Thanh, B.L., Ruggieri, S., Turini, F.: K-NN as an implementation of situation testing for discrimination discovery and prevention. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 502\u2013510 (2011)"},{"key":"16_CR48","doi-asserted-by":"crossref","unstructured":"Zafar, M.B., Valera, I., Rodriguez, M.G., Gummadi, K.P.: Fairness beyond disparate treatment & disparate impact: learning classification without disparate mistreatment. In: Proceedings of the 26th International Conference on World Wide Web (WWW), pp. 1171\u20131180 (2017)","DOI":"10.1145\/3038912.3052660"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-39479-0_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T22:15:54Z","timestamp":1614118554000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-39479-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030394783","9783030394790"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-39479-0_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"25 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 September 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 September 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo2019.ak.in.tum.de\/index.php\/menue-waoa\/waoa-overview","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}