{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,19]],"date-time":"2026-04-19T05:42:37Z","timestamp":1776577357840,"version":"3.51.2"},"reference-count":49,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100002822","name":"Central South University","doi-asserted-by":"publisher","award":["2023QYJC023"],"award-info":[{"award-number":["2023QYJC023"]}],"id":[{"id":"10.13039\/501100002822","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62432016"],"award-info":[{"award-number":["62432016"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62172446"],"award-info":[{"award-number":["62172446"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1016\/j.tcs.2026.115900","type":"journal-article","created":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T00:50:15Z","timestamp":1773967815000},"page":"115900","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Better guarantees for individual fairness k-median"],"prefix":"10.1016","volume":"1074","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-8626-1573","authenticated-orcid":false,"given":"Di","family":"Wu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-7309-5784","authenticated-orcid":false,"given":"Qilong","family":"Feng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1516-0480","authenticated-orcid":false,"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"1","key":"10.1016\/j.tcs.2026.115900_bib0001","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1006\/jagm.1998.0993","article-title":"Greedy strikes back: improved facility location algorithms","volume":"31","author":"Guha","year":"1999","journal-title":"J. Algor."},{"issue":"2","key":"10.1016\/j.tcs.2026.115900_bib0002","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","article-title":"Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation","volume":"48","author":"Jain","year":"2001","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/j.tcs.2026.115900_bib0003","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1137\/130938645","article-title":"Approximating k-median via pseudo-approximation","volume":"45","author":"Li","year":"2016","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2026.115900_bib0004","article-title":"Simpler analyses of local search algorithms for facility location","volume":"abs\/0809.2554","author":"Gupta","year":"2008","journal-title":"CoRR"},{"issue":"1","key":"10.1016\/j.tcs.2026.115900_bib0005","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/jcss.2002.1882","article-title":"A constant-factor approximation algorithm for the k-median problem","volume":"65","author":"Charikar","year":"2002","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"10.1016\/j.tcs.2026.115900_bib0006","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1145\/950620.950621","article-title":"Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP","volume":"50","author":"Jain","year":"2003","journal-title":"J. ACM"},{"issue":"3","key":"10.1016\/j.tcs.2026.115900_bib0007","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/S0097539702416402","article-title":"Local search heuristics for k-median and facility location problems","volume":"33","author":"Arya","year":"2004","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/j.tcs.2026.115900_bib0008","doi-asserted-by":"crossref","first-page":"23:1","DOI":"10.1145\/2981561","article-title":"An improved approximation for k-median and positive correlation in budgeted optimization","volume":"13","author":"Byrka","year":"2017","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"10.1016\/j.tcs.2026.115900_bib0009","doi-asserted-by":"crossref","DOI":"10.1007\/s11704-023-3355-7","article-title":"Constrained clustering with weak label prior","volume":"18","author":"Zhang","year":"2024","journal-title":"Front. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115900_bib0010","series-title":"Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms","first-page":"987","article-title":"Improved bi-point rounding algorithms and a golden barrier for k-median","author":"Gowda","year":"2023"},{"issue":"6","key":"10.1016\/j.tcs.2026.115900_bib0011","doi-asserted-by":"crossref","first-page":"44:1","DOI":"10.1145\/3477541","article-title":"Near-linear time approximation schemes for clustering in doubling metrics","volume":"68","author":"Cohen-Addad","year":"2021","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/j.tcs.2026.115900_bib0012","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1137\/17M112717X","article-title":"Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics","volume":"48","author":"Cohen-Addad","year":"2019","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/j.tcs.2026.115900_bib0013","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1137\/17M1127181","article-title":"Local search yields a PTAS for k-means in doubling metrics","volume":"48","author":"Friggstad","year":"2019","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2026.115900_bib0014","series-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","first-page":"281","article-title":"Bypassing the embedding: algorithms for low dimensional metrics","author":"Talwar","year":"2004"},{"key":"10.1016\/j.tcs.2026.115900_bib0015","series-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming","first-page":"42:1","article-title":"Tight FPT approximations for k-median and k-means","author":"Cohen-Addad","year":"2019"},{"key":"10.1016\/j.tcs.2026.115900_bib0016","series-title":"Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science","first-page":"743","article-title":"From gap-ETH to FPT-Inapproximability: clique, dominating set, and more","author":"Chalermsook","year":"2017"},{"key":"10.1016\/j.tcs.2026.115900_bib0017","series-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming","first-page":"78:1","article-title":"A birthday repetition theorem and complexity of approximating dense CSPs","author":"Manurangsi","year":"2017"},{"key":"10.1016\/j.tcs.2026.115900_bib0018","series-title":"Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms","first-page":"2241","article-title":"Approximation schemes for capacitated clustering in doubling metrics","author":"Cohen-Addad","year":"2020"},{"key":"10.1016\/j.tcs.2026.115900_bib0019","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.tcs.2022.11.027","article-title":"Improved approximation algorithms for solving the squared metric k-facility location problem","volume":"942","author":"Zhang","year":"2023","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10.1016\/j.tcs.2026.115900_bib0020","doi-asserted-by":"crossref","first-page":"1006","DOI":"10.1007\/s00453-018-0454-1","article-title":"Approximation algorithms for min-sum k-clustering and balanced k-median","volume":"81","author":"Behsaz","year":"2019","journal-title":"Algorithmica"},{"key":"10.1016\/j.tcs.2026.115900_bib0021","series-title":"Proceedings of the 1st Symposium on Foundations of Responsible Computing","first-page":"5:1","article-title":"Service in your neighborhood: fairness in center location","author":"Jung","year":"2020"},{"key":"10.1016\/j.tcs.2026.115900_bib0022","series-title":"Proceedings of the 37th International Conference on Machine Learning","first-page":"6586","article-title":"Individual fairness for k-clustering","author":"Mahabadi","year":"2020"},{"key":"10.1016\/j.tcs.2026.115900_bib0023","series-title":"Proceedings of the 34th Advances in Neural Information Processing Systems","first-page":"13340","article-title":"Better algorithms for individually fair k-clustering","author":"Negahbani","year":"2021"},{"key":"10.1016\/j.tcs.2026.115900_bib0024","series-title":"Proceedings of the 47th IEEE International Conference on Acoustics, Speech and Signal Processing","first-page":"4433","article-title":"No more than 6ft apart: robust k-means via radius upper bounds","author":"Humayun","year":"2022"},{"key":"10.1016\/j.tcs.2026.115900_bib0025","series-title":"Proceedings of the 25th International Conference on Artificial Intelligence and Statistics","first-page":"8758","article-title":"Improved approximation algorithms for individually fair clustering","author":"Vakilian","year":"2022"},{"key":"10.1016\/j.tcs.2026.115900_bib0026","series-title":"Proceedings of the 27th International Conference on Artificial Intelligence and Statistics","first-page":"3151","article-title":"A scalable algorithm for individually fair k-means clustering","author":"Bateni","year":"2024"},{"issue":"4","key":"10.1016\/j.tcs.2026.115900_bib0027","doi-asserted-by":"crossref","DOI":"10.1137\/18M1171321","article-title":"Better guarantees for k-means and euclidean k-median by primal-dual algorithms","volume":"49","author":"Ahmadian","year":"2020","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2026.115900_bib0028","first-page":"5029","article-title":"Fair clustering through fairlets","author":"Chierichetti","year":"2017","journal-title":"Proc. 31st Adv. Neural Inf. Process. Syst."},{"key":"10.1016\/j.tcs.2026.115900_bib0029","series-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming","first-page":"96:1","article-title":"Privacy preserving clustering with constraints","author":"R\u00f6sner","year":"2018"},{"key":"10.1016\/j.tcs.2026.115900_bib0030","series-title":"Proceedings of the 33rd Advances in Neural Information Processing Systems","first-page":"4955","article-title":"Fair algorithms for clustering","author":"Bera","year":"2019"},{"key":"10.1016\/j.tcs.2026.115900_bib0031","series-title":"Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining","first-page":"267","article-title":"Clustering without over-representation","author":"Ahmadian","year":"2019"},{"key":"10.1016\/j.tcs.2026.115900_bib0032","series-title":"Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics","first-page":"4195","article-title":"Fair correlation clustering","author":"Ahmadian","year":"2020"},{"key":"10.1016\/j.tcs.2026.115900_bib0033","series-title":"Proceedings of the 40th International Conference on Machine Learning","first-page":"13270","article-title":"Approximation algorithms for fair range clustering","author":"Hotegni","year":"2023"},{"issue":"5","key":"10.1016\/j.tcs.2026.115900_bib0034","doi-asserted-by":"crossref","first-page":"1959","DOI":"10.1007\/s10618-023-00928-6","article-title":"Efficient algorithms for fair clustering with a new notion of fairness","volume":"37","author":"Gupta","year":"2023","journal-title":"Data Min. Knowl. Discov."},{"key":"10.1016\/j.tcs.2026.115900_bib0035","series-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing","first-page":"620","article-title":"Constant-factor approximation for ordered k-median","author":"Byrka","year":"2018"},{"key":"10.1016\/j.tcs.2026.115900_bib0036","series-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming","first-page":"29:1","article-title":"Interpolating between k-median and k-center: approximation algorithms for ordered k-median","author":"Chakrabarty","year":"2018"},{"key":"10.1016\/j.tcs.2026.115900_bib0037","series-title":"Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"2664","article-title":"Approximating fair clustering with cascaded norm objectives","author":"Chlamt\u00e1\u010d","year":"2022"},{"key":"10.1016\/j.tcs.2026.115900_bib0038","series-title":"Proceedings of the 4th ACM Conference on Fairness, Accountability, and Transparency","first-page":"438","article-title":"Socially fair k-means clustering","author":"Ghadiri","year":"2021"},{"key":"10.1016\/j.tcs.2026.115900_bib0039","series-title":"Proceedings of the 4th ACM Conference on Fairness, Accountability, and Transparency","first-page":"504","article-title":"Fair clustering via equitable group representations","author":"Abbasi","year":"2021"},{"key":"10.1016\/j.tcs.2026.115900_bib0040","series-title":"Proceedings of the 34th Conference on Learning Theory","first-page":"3246","article-title":"Approximation algorithms for socially fair clustering","author":"Makarychev","year":"2021"},{"key":"10.1016\/j.tcs.2026.115900_bib0041","series-title":"Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","first-page":"551","article-title":"Kernel k-means: spectral clustering and normalized cuts","author":"Dhillon","year":"2004"},{"key":"10.1016\/j.tcs.2026.115900_bib0042","series-title":"Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence","first-page":"799","article-title":"Robust k-means++","author":"Deshpande","year":"2020"},{"key":"10.1016\/j.tcs.2026.115900_bib0043","series-title":"Proceedings of the 30th Advances in Neural Information Processing Systems","first-page":"2883","article-title":"Robust k-means: a theoretical revisit","author":"Georgogiannis","year":"2016"},{"key":"10.1016\/j.tcs.2026.115900_bib0044","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","article-title":"Clustering to minimize the maximum intercluster distance","volume":"38","author":"Gonzalez","year":"1985","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115900_bib0045","series-title":"Proceedings of the 28th International Conference on Artificial Intelligence and Statistics","first-page":"2287","article-title":"A subquadratic time approximation algorithm for individually fair k-center","author":"Ebbens","year":"2025"},{"key":"10.1016\/j.tcs.2026.115900_bib0046","series-title":"Proceedings of the 30th Annual ACM Symposium on the Theory of Computing","first-page":"106","article-title":"Approximation schemes for Euclidean k-medians and related problems","author":"Arora","year":"1998"},{"issue":"3","key":"10.1016\/j.tcs.2026.115900_bib0047","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1137\/S0097539702404055","article-title":"A nearly linear-time approximation scheme for the Euclidean k-median problem","volume":"37","author":"Kolliopoulos","year":"2007","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2026.115900_bib0048","series-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science","first-page":"534","article-title":"Bounded geometries, fractals, and low-distortion embeddings","author":"Gupta","year":"2003"},{"key":"10.1016\/j.tcs.2026.115900_bib0049","series-title":"Proceedings of the 54th Annual Symposium on Foundations of Computer Science","first-page":"698","article-title":"A linear time approximation scheme for Euclidean TSP","author":"Bartal","year":"2013"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526001593?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526001593?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,4,19]],"date-time":"2026-04-19T05:06:23Z","timestamp":1776575183000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397526001593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6]]},"references-count":49,"alternative-id":["S0304397526001593"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115900","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,6]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Better guarantees for individual fairness k-median","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115900","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}],"article-number":"115900"}}