{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T23:34:54Z","timestamp":1772580894331,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,7,8]],"date-time":"2019-07-08T00:00:00Z","timestamp":1562544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"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            We study the \u2131-center problem with outliers: Given a metric space (\n            <jats:italic>X<\/jats:italic>\n            ,\n            <jats:italic>d<\/jats:italic>\n            ), a general down-closed family \u2131 of subsets of\n            <jats:italic>X<\/jats:italic>\n            , and a parameter\n            <jats:italic>m<\/jats:italic>\n            , we need to locate a subset\n            <jats:italic>S<\/jats:italic>\n            \u2208 \u2131 of centers such that the maximum distance among the closest\n            <jats:italic>m<\/jats:italic>\n            points in\n            <jats:italic>X<\/jats:italic>\n            to\n            <jats:italic>S<\/jats:italic>\n            is minimized. Our main result is a\n            <jats:italic>dichotomy theorem<\/jats:italic>\n            . Colloquially, we prove that there is an efficient 3-approximation for the \u2131-center problem with outliers if and only if we can efficiently optimize a\n            <jats:italic>poly-bounded<\/jats:italic>\n            linear function over \u2131 subject to a partition constraint. One concrete upshot of our result is a polynomial time 3-approximation for the knapsack center problem with outliers for which no (true) approximation algorithm was known.\n          <\/jats:p>","DOI":"10.1145\/3338513","type":"journal-article","created":{"date-parts":[[2019,7,9]],"date-time":"2019-07-09T12:45:29Z","timestamp":1562676329000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Generalized Center Problems with Outliers"],"prefix":"10.1145","volume":"15","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[{"name":"Dartmouth College, NH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maryam","family":"Negahbani","sequence":"additional","affiliation":[{"name":"Dartmouth College, NH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,7,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798602"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.35"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0307-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90018-8"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900)","author":"Carr Robert D.","unstructured":"Robert D. Carr , Lisa K. Fleischer , Vitus J. Leung , and Cynthia A. Phillips . 2000. Strengthening integrality gaps for capacitated network design and covering problems . In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 106--115. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=338219.338241. Robert D. Carr, Lisa K. Fleischer, Vitus J. Leung, and Cynthia A. Phillips. 2000. Strengthening integrality gaps for capacitated network design and covering problems. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900). Society for Industrial and Applied Mathematics, Philadelphia, PA, 106--115. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=338219.338241."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","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) . 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). 67:1--67:15."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_11"},{"key":"e_1_2_1_8_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. 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."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133118"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_10"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0703-7"},{"key":"e_1_2_1_13_1","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel Martin","unstructured":"Martin Gr\u00f6tschel , L\u00e1szl\u00f3 Lov\u00e1sz , and Alexander Schriver . 1993. Geometric Algorithms and Combinatorial Optimization . Springer , Berlin . Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schriver. 1993. Geometric Algorithms and Combinatorial Optimization. Springer, Berlin."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.12.3.450"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.13.3.462"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201917)","author":"Harris David G.","year":"2017","unstructured":"David G. Harris , Thomas Pensyl , Aravind Srinivasan , and Khoa Trinh . 2017 . A lottery model for center-type problems with outliers . In Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201917) . 10:1--10:19. David G. Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh. 2017. A lottery model for center-type problems with outliers. In Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201917). 10:1--10:19."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.180"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5933"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(79)90044-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722176"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884491"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.383347"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/322307.322309"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3338513","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3338513","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:46Z","timestamp":1750203886000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3338513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,8]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3338513"],"URL":"https:\/\/doi.org\/10.1145\/3338513","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,8]]},"assertion":[{"value":"2018-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}