{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T20:33:54Z","timestamp":1770064434578,"version":"3.49.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T00:00:00Z","timestamp":1560297600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006785","name":"Google LLC","doi-asserted-by":"crossref","award":["Gift"],"award-info":[{"award-number":["Gift"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1010789"],"award-info":[{"award-number":["CNS-1010789"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Adobe Inc","award":["Gift"],"award-info":[{"award-number":["Gift"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>\n            In this article, we give tight approximation algorithms for the\n            <jats:italic>k<\/jats:italic>\n            -center and matroid center problems with outliers. Unfairness arises naturally in this setting: certain clients could always be considered as outliers. To address this issue, we introduce a lottery model in which each client\n            <jats:italic>j<\/jats:italic>\n            is allowed to submit a parameter\n            <jats:italic>p<\/jats:italic>\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            \u2208 [0,1] and we look for a random solution that covers every client\n            <jats:italic>j<\/jats:italic>\n            with probability at least\n            <jats:italic>p<\/jats:italic>\n            <jats:sub>\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            . Our techniques include a randomized rounding procedure to round a point inside a matroid intersection polytope to a basis plus at most one extra item such that all marginal probabilities are preserved and such that a certain linear function of the variables does not decrease in the process with probability one.\n          <\/jats:p>","DOI":"10.1145\/3311953","type":"journal-article","created":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T12:09:28Z","timestamp":1560427768000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["A Lottery Model for Center-Type Problems With Outliers"],"prefix":"10.1145","volume":"15","author":[{"given":"David G.","family":"Harris","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Maryland, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Pensyl","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khoa","family":"Trinh","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Sara Ahmadian Ashkan Norouzi-Fard Ola Svensson and Justin Ward. 2016. Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. CoRR abs\/1612.07925. http:\/\/arxiv.org\/abs\/1612.07925  Sara Ahmadian Ashkan Norouzi-Fard Ola Svensson and Justin Ward. 2016. Better guarantees for k -means and Euclidean k -median by primal-dual algorithms. CoRR abs\/1612.07925. http:\/\/arxiv.org\/abs\/1612.07925"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.50"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","volume":"55","author":"Chakrabarty Deeparnab","year":"2016","unstructured":"Deeparnab Chakrabarty , Prachi Goyal , and Ravishankar Krishnaswamy . 2016 . The non-uniform k-center problem . In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916) , Vol. 55 . 67:1--67:15. Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. 2016. The non-uniform k-center problem. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916), Vol. 55. 67:1--67:15."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901)","author":"Charikar Moses","year":"2001","unstructured":"Moses Charikar , Samir Khuller , David M. Mount , and Giri Narasimhan . 2001 . Algorithms for facility location problems with outliers . In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 642--651. http:\/\/dl.acm.org\/citation.cfm?id&equals;365411.365555 Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. 2001. Algorithms for facility location problems with outliers. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901). Society for Industrial and Applied Mathematics, Philadelphia, PA, 642--651. http:\/\/dl.acm.org\/citation.cfm?id&equals;365411.365555"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_10"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1987v042n02ABEH001308"},{"key":"e_1_2_1_7_1","unstructured":"David G. Harris Thomas Pensyl Aravind Srinivasan and Khoa Trinh. 2017. Symmetric randomized dependent rounding. CoRR abs\/1709.06995.  David G. Harris Thomas Pensyl Aravind Srinivasan and Khoa Trinh. 2017. Symmetric randomized dependent rounding. CoRR abs\/1709.06995."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5933"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(79)90044-1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.84"},{"key":"e_1_2_1_12_1","volume-title":"Iterative Methods in Combinatorial Optimization","author":"Lau Lap-Chi","unstructured":"Lap-Chi Lau , R. Ravi , and Mohit Singh . 2011. Iterative Methods in Combinatorial Optimization ( 1 st ed.). Cambridge University Press, New York , NY. Lap-Chi Lau, R. Ravi, and Mohit Singh. 2011. Iterative Methods in Combinatorial Optimization (1st ed.). Cambridge University Press, New York, NY.","edition":"1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488723"},{"key":"e_1_2_1_14_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency.","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver . 2003 . Combinatorial Optimization: Polyhedra and Efficiency. Vol. 24 . Springer Science 8 Business Media. Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Vol. 24. Springer Science 8 Business Media."},{"key":"e_1_2_1_15_1","volume-title":"APPROX\/RANDOM","volume":"28","author":"Swamy Chaitanya","year":"2014","unstructured":"Chaitanya Swamy . 2014 . Improved approximation algorithms for matroid and knapsack median problems and applications . In APPROX\/RANDOM 2014, Vol. 28 . 403--418. Chaitanya Swamy. 2014. Improved approximation algorithms for matroid and knapsack median problems and applications. In APPROX\/RANDOM 2014, Vol. 28. 403--418."},{"key":"e_1_2_1_16_1","volume-title":"Shmoys","author":"Williamson David P.","year":"2011","unstructured":"David P. Williamson and David B . Shmoys . 2011 . The Design of Approximation Algorithms. Cambridge University Press . I--XI, 1--504 pages. David P. Williamson and David B. Shmoys. 2011. The Design of Approximation Algorithms. Cambridge University Press. I--XI, 1--504 pages."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3311953","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3311953","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3311953","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:12Z","timestamp":1750204392000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3311953"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,12]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3311953"],"URL":"https:\/\/doi.org\/10.1145\/3311953","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,12]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}