{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T01:19:44Z","timestamp":1777339184523,"version":"3.51.4"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T00:00:00Z","timestamp":1625097600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T00:00:00Z","timestamp":1625097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021-184656"],"award-info":[{"award-number":["200021-184656"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An instance of <jats:italic>colorful<\/jats:italic><jats:italic>k<\/jats:italic>-<jats:italic>center<\/jats:italic> consists of points in a metric space that are colored red or blue, along with an integer <jats:italic>k<\/jats:italic> and a coverage requirement for each color. The goal is to find the smallest radius <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\rho $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c1<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that there exist balls of radius <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\rho $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c1<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> around <jats:italic>k<\/jats:italic> of the points that meet the coverage requirements. The motivation behind this problem is twofold. First, from fairness considerations: each color\/group should receive a similar service guarantee, and second, from the algorithmic challenges it poses: this problem combines the difficulties of clustering along with the subset-sum problem. In particular, we show that this combination results in strong integrality gap lower bounds for several natural linear programming relaxations. Our main result is an efficient approximation algorithm that overcomes these difficulties to achieve an approximation guarantee of 3, nearly matching the tight approximation guarantee of 2 for the classical <jats:italic>k<\/jats:italic>-center problem which this problem generalizes. algorithms either opened more than <jats:italic>k<\/jats:italic> centers or only worked in the special case when the input points are in the plane.<\/jats:p>","DOI":"10.1007\/s10107-021-01674-7","type":"journal-article","created":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T09:03:20Z","timestamp":1625130200000},"page":"339-360","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Fair colorful k-center clustering"],"prefix":"10.1007","volume":"192","author":[{"given":"Xinrui","family":"Jia","sequence":"first","affiliation":[]},{"given":"Kshiteej","family":"Sheth","sequence":"additional","affiliation":[]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,1]]},"reference":[{"key":"1674_CR1","unstructured":"Anagnostopoulos, A., Becchetti, L., B\u00f6hm, M., Fazzone, A., Leonardi, S., Menghini, C., Schwiegelshohn, C.: Principal fairness: removing bias via projections. CoRR arXiv:1905.13651 (2019)"},{"key":"1674_CR2","doi-asserted-by":"crossref","unstructured":"Anegg, G., Angelidakis, H., Kurpisz, A., Zenklusen, R.: A technique for obtaining true approximations for k-center with covering constraints. In: International Conference on Integer Programming and Combinatorial Optimization (IPCO). pp. 52\u201365 (2020)","DOI":"10.1007\/978-3-030-45771-6_5"},{"key":"1674_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Ge, R.: New tools for graph coloring. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. pp. 1\u201312. Springer (2011)","DOI":"10.1007\/978-3-642-22935-0_1"},{"key":"1674_CR4","unstructured":"Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., Wagner, T.: Scalable fair clustering. In: Proceedings of the 36th International Conference on Machine Learning, ICML. pp. 405\u2013413 (2019)"},{"key":"1674_CR5","unstructured":"Bandyapadhyay, S., Inamdar, T., Pai, S., Varadarajan, K.R.: A constant approximation for colorful k-center. In: 27th Annual European Symposium on Algorithms, ESA. pp. 1\u201314 (2019)"},{"key":"1674_CR6","unstructured":"Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The non-uniform k-center problem. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP. pp. 1\u201315 (2016)"},{"key":"1674_CR7","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 (SODA). pp. 642\u2013651 (2001)"},{"key":"1674_CR8","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. In: Advances in Neural Information Processing Systems (NIPS). pp. 5029\u20135037 (2017)"},{"key":"1674_CR9","unstructured":"Chlamtac, E., Friggstad, Z., Georgiou, K.: Understanding set cover: Sub-exponential time approximations and lift-and-project methods. CoRR arXiv:1204.5489 (2012)"},{"key":"1674_CR10","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. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1674_CR11","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00037-001-8192-0","volume":"10","author":"D Grigoriev","year":"2001","unstructured":"Grigoriev, D.: Complexity of positivstellensatz proofs for the knapsack. Comput. Complex. 10(2), 139\u2013154 (2001)","journal-title":"Comput. Complex."},{"issue":"3","key":"1674_CR12","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":"1674_CR13","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."},{"issue":"3","key":"1674_CR14","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0166-218X(79)90044-1","volume":"1","author":"WL Hsu","year":"1979","unstructured":"Hsu, W.L., Nemhauser, G.L.: Easy and hard bottleneck location problems. Discret. Appl. Math. 1(3), 209\u2013215 (1979)","journal-title":"Discret. Appl. Math."},{"key":"1674_CR15","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Mathieu, C., Nguyen, C.T.: Integrality gaps of linear and semi-definite programming relaxations for knapsack. In: Integer Programming and Combinatoral Optimization IPCO. pp. 301\u2013314 (2011)","DOI":"10.1007\/978-3-642-20807-2_24"},{"key":"1674_CR16","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: International Conference on Integer Programming and Combinatorial Optimization (IPCO). pp. 293\u2013303 (2001)","DOI":"10.1007\/3-540-45535-3_23"},{"issue":"3","key":"1674_CR17","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"key":"1674_CR18","doi-asserted-by":"crossref","unstructured":"Tulsiani, M.: CSP gaps and reductions in the lasserre hierarchy. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC. pp. 303\u2013312 (2009)","DOI":"10.1145\/1536414.1536457"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01674-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01674-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01674-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T17:19:13Z","timestamp":1646846353000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01674-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,1]]},"references-count":18,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1674"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01674-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,1]]},"assertion":[{"value":"30 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}