{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T18:29:01Z","timestamp":1743013741909,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031393433"},{"type":"electronic","value":"9783031393440"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-39344-0_17","type":"book-chapter","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T20:27:10Z","timestamp":1692995230000},"page":"225-238","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Fair k-Center with\u00a0Outliers Problem: FPT and\u00a0Polynomial Approximations"],"prefix":"10.1007","author":[{"given":"Xiaoliang","family":"Wu","sequence":"first","affiliation":[]},{"given":"Qilong","family":"Feng","sequence":"additional","affiliation":[]},{"given":"Jinhui","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,26]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., et al.: Achieving anonymity via clustering. ACM Trans. Algorithms 6(3), 49:1\u201349:19 (2010)","DOI":"10.1145\/1798596.1798602"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Ahmadian, S., Epasto, A., Kumar, R., Mahdian, M.: Clustering without over-representation. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 267\u2013275 (2019)","DOI":"10.1145\/3292500.3330987"},{"key":"17_CR3","unstructured":"Ahmadian, S., Swamy, C.: Approximation algorithms for clustering problems with lower bounds and outliers. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, pp. 69:1\u201369:15 (2016)"},{"issue":"1\u20132","key":"17_CR4","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s10107-014-0857-y","volume":"154","author":"H An","year":"2015","unstructured":"An, H., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V., Svensson, O.: Centrality of trees for capacitated $$k$$-center. Math. Program. 154(1\u20132), 29\u201353 (2015)","journal-title":"Math. Program."},{"key":"17_CR5","unstructured":"Angelidakis, H., Kurpisz, A., Sering, L., Zenklusen, R.: Fair and fast $$k$$-center clustering for data summarization. In: Proceedings of the 39th International Conference on Machine Learning, pp. 669\u2013702 (2022)"},{"key":"17_CR6","unstructured":"Belkin, M.: Problems of learning on manifolds. The University of Chicago (2004)"},{"key":"17_CR7","unstructured":"Bera, S.K., Chakrabarty, D., Flores, N., Negahbani, M.: Fair algorithms for clustering. In: Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 4955\u20134966 (2019)"},{"key":"17_CR8","unstructured":"Bercea, I.O., Gro\u00df, M., Khuller, S., Kumar, A., R\u00f6sner, C., Schmidt, D.R., Schmidt, M.: On the cost of essentially fair clusterings. In: Proceedings of the 22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, pp. 18:1\u201318:22 (2019)"},{"issue":"7","key":"17_CR9","doi-asserted-by":"publisher","first-page":"766","DOI":"10.14778\/3317315.3317319","volume":"12","author":"M Ceccarello","year":"2019","unstructured":"Ceccarello, M., Pietracaprina, A., Pucci, G.: Solving $$k$$-center clustering (with outliers) in mapreduce and streaming, almost as accurately as sequentially. Proc. VLDB Endowment 12(7), 766\u2013778 (2019)","journal-title":"Proc. VLDB Endowment"},{"key":"17_CR10","unstructured":"Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The non-uniform $$k$$-center problem. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, pp. 67:1\u201367:15 (2016)"},{"issue":"4","key":"17_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3392720","volume":"16","author":"D Chakrabarty","year":"2020","unstructured":"Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The non-uniform $$k$$-center problem. ACM Trans. Algorithms 16(4), 1\u201319 (2020)","journal-title":"ACM Trans. Algorithms"},{"key":"17_CR12","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 642\u2013651 (2001)"},{"key":"17_CR13","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.tcs.2014.11.017","volume":"566","author":"S Chechik","year":"2015","unstructured":"Chechik, S., Peleg, D.: The fault-tolerant capacitated $$k$$-center problem. Theoret. Comput. Sci. 566, 12\u201325 (2015)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"17_CR14","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s00453-015-0010-1","volume":"75","author":"DZ Chen","year":"2016","unstructured":"Chen, D.Z., Li, J., Liang, H., Wang, H.: Matroid and knapsack center problems. Algorithmica 75(1), 27\u201352 (2016)","journal-title":"Algorithmica"},{"key":"17_CR15","unstructured":"Chen, X., Fain, B., Lyu, L., Munagala, K.: Proportionally fair clustering. In: Proceedings of the 36th International Conference on Machine Learning, pp. 1032\u20131041 (2019)"},{"key":"17_CR16","unstructured":"Chiplunkar, A., Kale, S., Ramamoorthy, S.N.: How to solve fair $$k$$-center in massive data models. In: Proceedings of the 37th International Conference on Machine Learning, pp. 1877\u20131886 (2020)"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Cygan, M., Hajiaghayi, M., Khuller, S.: LP rounding for $$k$$-centers with non-uniform hard capacities. In: Proceedings of the 53rd Annual Symposium on Foundations of Computer Science, pp. 273\u2013282 (2012)","DOI":"10.1109\/FOCS.2012.63"},{"key":"17_CR18","unstructured":"Daniely, A., Linial, N., Saks, M.: Clustering is difficult only when it does not matter. arXiv preprint arXiv:1205.4891 (2012)"},{"key":"17_CR19","unstructured":"Ding, H., Yu, H., Wang, Z.: Greedy strategy works for $$k$$-center clustering with outliers and coreset construction. In: Proceedings of the 27th Annual European Symposium on Algorithms, pp. 40:1\u201340:16 (2019)"},{"issue":"3","key":"17_CR20","doi-asserted-by":"publisher","first-page":"1041","DOI":"10.1007\/s00453-017-0398-x","volume":"80","author":"CG Fernandes","year":"2018","unstructured":"Fernandes, C.G., de Paula, S.P., Pedrosa, L.L.C.: Improved approximation algorithms for capacitated fault-tolerant $$k$$-center. Algorithmica 80(3), 1041\u20131072 (2018)","journal-title":"Algorithmica"},{"key":"17_CR21","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399\u2013404 (1956)","journal-title":"Can. J. Math."},{"key":"17_CR22","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman (1979)"},{"key":"17_CR23","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theoret. Comput. Sci."},{"key":"17_CR24","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.tcs.2022.11.001","volume":"940","author":"D Goyal","year":"2023","unstructured":"Goyal, D., Jaiswal, R.: Tight FPT approximation for constrained $$k$$-center and $$k$$-supplier. Theoret. Comput. Sci. 940, 190\u2013208 (2023)","journal-title":"Theoret. Comput. Sci."},{"key":"17_CR25","doi-asserted-by":"crossref","unstructured":"Han, L., Xu, D., Xu, Y., Yang, P.: Approximation algorithms for the individually fair $$k$$-center with outliers. J. Glob. Optim. 1\u201316 (2022)","DOI":"10.1007\/s10898-022-01195-3"},{"key":"17_CR26","unstructured":"Harb, E., Lam, H.S.: KFC: A scalable approximation algorithm for $$k$$-center fair clustering. In: Proceedings of the 34th International Conference on Neural Information Processing Systems, pp. 14509\u201314519 (2020)"},{"issue":"3","key":"17_CR27","first-page":"1","volume":"15","author":"DG Harris","year":"2019","unstructured":"Harris, D.G., Pensyl, T., Srinivasan, A., Trinh, K.: A lottery model for center-type problems with outliers. ACM Trans. Algorithms 15(3), 1\u201325 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"17_CR28","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the $$k$$-center problem. Math. Oper. Res. 10(2), 180\u2013184 (1985)","journal-title":"Math. Oper. Res."},{"key":"17_CR29","unstructured":"Jones, M., L\u00ea Nguy\u00ean, H., Nguyen, T.: Fair $$k$$-centers via maximum matching. In: Proceedings of the 37th International Conference on Machine Learning, pp. 4940\u20134949 (2020)"},{"issue":"7","key":"17_CR30","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."},{"issue":"1\u20132","key":"17_CR31","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(98)00222-9","volume":"242","author":"S Khuller","year":"2000","unstructured":"Khuller, S., Pless, R., Sussmann, Y.J.: Fault tolerant $$k$$-center problems. Theoret. Comput. Sci. 242(1\u20132), 237\u2013245 (2000)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"17_CR32","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/S0895480197329776","volume":"13","author":"S Khuller","year":"2000","unstructured":"Khuller, S., Sussmann, Y.J.: The capacitated $$k$$-center problem. SIAM J. Discret. Math. 13(3), 403\u2013418 (2000)","journal-title":"SIAM J. Discret. Math."},{"key":"17_CR33","unstructured":"Kleindessner, M., Awasthi, P., Morgenstern, J.: Fair $$k$$-center clustering for data summarization. In: Proceeding of the 36th International Conference on Machine Learning, pp. 3448\u20133457 (2019)"},{"key":"17_CR34","unstructured":"Li, B., Li, L., Sun, A., Wang, C., Wang, Y.: Approximate group fairness for clustering. In: Proceedings of the 38th International Conference on Machine Learning, pp. 6381\u20136391 (2021)"},{"key":"17_CR35","unstructured":"Mahabadi, S., Vakilian, A.: Individual fairness for $$k$$-clustering. In: Proceedings of the 37th International Conference on Machine Learning, pp. 6586\u20136596 (2020)"},{"key":"17_CR36","unstructured":"Malkomes, G., Kusner, M.J., Chen, W., Weinberger, K.Q., Moseley, B.: Fast distributed $$k$$-center clustering with outliers on massive data. In: Advances in Neural Information Processing Systems, vol. 28 (2015)"},{"key":"17_CR37","unstructured":"Micha, E., Shah, N.: Proportionally fair clustering revisited. In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, pp. 85:1\u201385:16 (2020)"},{"key":"17_CR38","unstructured":"Negahbani, M., Chakrabarty, D.: Better algorithms for individually fair $$k$$-clustering. In: Proceedings of the 35th International Conference on Neural Information Processing Systems, pp. 13340\u201313351 (2021)"},{"key":"17_CR39","doi-asserted-by":"crossref","unstructured":"Yuan, F., Diao, L., Du, D., Liu, L.: Distributed fair $$k$$-center clustering problems with outliers. In: Proceedings of the 22nd International Conference on Parallel and Distributed Computing, Applications and Technologies, pp. 430\u2013440 (2022)","DOI":"10.1007\/978-3-030-96772-7_39"}],"container-title":["Lecture Notes in Computer Science","Frontiers of Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-39344-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T20:28:26Z","timestamp":1692995306000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-39344-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031393433","9783031393440"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-39344-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"26 August 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IJTCS-FAW","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Frontiers in Algorithmics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Macau","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 August 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2023","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":"faw2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conferences.cis.um.edu.mo\/ijtcs2023\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"34","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"62% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}