{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T18:06:29Z","timestamp":1789149989083,"version":"build-2803163510"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T00:00:00Z","timestamp":1789084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2041920"],"award-info":[{"award-number":["CCF-2041920"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2026,9,30]]},"abstract":"<jats:p>\n                    We present approximation algorithms for the Fault-tolerant\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -Supplier with Outliers (\n                    <jats:sans-serif>\n                      F\n                      <jats:italic toggle=\"yes\">k<\/jats:italic>\n                      SO\n                    <\/jats:sans-serif>\n                    ) problem. This is a common generalization of two known problems \u2013\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -Supplier with Outliers, and Fault-tolerant\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -Supplier \u2013 each of which generalize the well-known\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -Supplier problem. In the\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -Supplier problem the goal is to serve\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    clients\n                    <jats:italic toggle=\"yes\">C<\/jats:italic>\n                    , by opening\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    facilities from a set of possible facilities\n                    <jats:italic toggle=\"yes\">F<\/jats:italic>\n                    ; the objective function is the farthest that any client must travel to access an open facility. In\n                    <jats:sans-serif>\n                      F\n                      <jats:italic toggle=\"yes\">k<\/jats:italic>\n                      SO\n                    <\/jats:sans-serif>\n                    , each client\n                    <jats:italic toggle=\"yes\">v<\/jats:italic>\n                    has a\n                    <jats:italic toggle=\"yes\">fault-tolerance<\/jats:italic>\n                    <jats:italic toggle=\"yes\">\n                      \u2113\n                      <jats:sub>v<\/jats:sub>\n                    <\/jats:italic>\n                    , and now desires\n                    <jats:italic toggle=\"yes\">\n                      \u2113\n                      <jats:sub>v<\/jats:sub>\n                    <\/jats:italic>\n                    facilities to serve it; so each client\n                    <jats:italic toggle=\"yes\">v<\/jats:italic>\n                    \u2019s contribution to the objective function is now its distance to the\n                    <jats:italic toggle=\"yes\">\n                      \u2113\n                      <jats:sub>v<\/jats:sub>\n                    <\/jats:italic>\n                    th closest open facility. Furthermore, we are allowed to choose\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    clients that we will serve, and only those clients contribute to the objective function, while the remaining\n                    <jats:italic toggle=\"yes\">n-m<\/jats:italic>\n                    are considered outliers.\n                  <\/jats:p>\n                  <jats:p>\n                    Our main result is a\n                    <jats:italic toggle=\"yes\">(4t-1)<\/jats:italic>\n                    -approximation for the\n                    <jats:sans-serif>\n                      F\n                      <jats:italic toggle=\"yes\">k<\/jats:italic>\n                      SO\n                    <\/jats:sans-serif>\n                    problem, where\n                    <jats:italic toggle=\"yes\">t<\/jats:italic>\n                    is the number of distinct values of\n                    <jats:italic toggle=\"yes\">\n                      \u2113\n                      <jats:sub>v<\/jats:sub>\n                    <\/jats:italic>\n                    that appear in the instance. At\n                    <jats:italic toggle=\"yes\">t=1<\/jats:italic>\n                    , i.e. in the case where the\n                    <jats:italic toggle=\"yes\">\n                      \u2113\n                      <jats:sub>v<\/jats:sub>\n                    <\/jats:italic>\n                    \u2019s are uniformly some\n                    <jats:italic toggle=\"yes\">\u2113<\/jats:italic>\n                    , this yields a 3-approximation, improving upon the 11-approximation given for the uniform case by Inamdar and Varadarajan [2020], who also introduced the problem. Our result for the uniform case matches tight 3-approximations that exist for\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -Supplier,\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -Supplier with Outliers, and Fault-tolerant\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -Supplier.\n                  <\/jats:p>\n                  <jats:p>\n                    Our key technical contribution is an application of the\n                    <jats:italic toggle=\"yes\">round-or-cut<\/jats:italic>\n                    schema to\n                    <jats:sans-serif>\n                      F\n                      <jats:italic toggle=\"yes\">k<\/jats:italic>\n                      SO\n                    <\/jats:sans-serif>\n                    . Guided by an LP relaxation, we reduce to a simpler optimization problem, which we can solve to obtain distance bounds for the \u201cround\u201d step, and valid inequalities for the \u201ccut\u201d step. By varying how we reduce to the simpler problem, we get varying distance bounds\u2014we include a variant that gives a\n                    <jats:italic toggle=\"yes\">\n                      (2\n                      <jats:sup>t<\/jats:sup>\n                      + 1)\n                    <\/jats:italic>\n                    -approximation, which is better for\n                    <jats:italic toggle=\"yes\">t \u2208 { 2,3}<\/jats:italic>\n                    . In addition, for\n                    <jats:italic toggle=\"yes\">t=1<\/jats:italic>\n                    , we give a more straightforward application of round-or-cut, yielding a 3-approximation, that is, much simpler than our general algorithm.\n                  <\/jats:p>","DOI":"10.1145\/3799696","type":"journal-article","created":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T11:09:47Z","timestamp":1772536187000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fault-tolerant\n                    <i>k<\/i>\n                    -Supplier with Outliers"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7596-6035","authenticated-orcid":false,"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[{"name":"Computer Science, Dartmouth College","place":["Hanover, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-3220-7289","authenticated-orcid":false,"given":"Luc","family":"Cote","sequence":"additional","affiliation":[{"name":"Operations Research Center, Massachusetts Institute of Technology","place":["Cambridge, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6787-7286","authenticated-orcid":false,"given":"Ankita","family":"Sarkar","sequence":"additional","affiliation":[{"name":"Computer Science, Dartmouth College","place":["Hanover, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,9,11]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","unstructured":"Ravinder Ahuja Aakarsha Chug Shaurya Gupta Pratyush Ahuja and Shruti Kohli. 2020. Classification and clustering algorithms of machine learning with their applications. Nature-Inspired Computation in Data Mining and Machine Learning 855 (2020) 225\u2013248. DOI:10.1007\/978-3-030-28553-1_11","DOI":"10.1007\/978-3-030-28553-1_11"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/151002320"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","unstructured":"Georg Anegg Haris Angelidakis Adam Kurpisz and Rico Zenklusen. 2022. A technique for obtaining true approxi-mations for \\(k\\) -center with covering constraints. Math. Programming 192 (2022) 1\u201325. DOI:10.1007\/s10107-021-01645-y","DOI":"10.1007\/s10107-021-01645-y"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.21"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","unstructured":"Deeparnab Chakrabarty Prachi Goyal and Ravishankar Krishnaswamy. 2020. The non-uniform \\(k\\) -center problem. ACM Trans. on Algorithms (TALG) 16 4 (2020) 1\u201319. DOI:10.1145\/3392720. Preliminary version in ICALP 2016.","DOI":"10.1145\/3392720"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","unstructured":"Deeparnab Chakrabarty and Maryam Negahbani. 2019. Generalized center problems with outliers. ACM Trans. on Algorithms (TALG) 15 3 (2019) 1\u201314. DOI:10.1145\/3338513. Prelim. version in ICALP 2018.","DOI":"10.1145\/3338513"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01799-3"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2022.33"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/365411.365555"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00224-X"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.05.013"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90167-2"},{"key":"e_1_3_2_15_2","unstructured":"Shichuan Deng. 2020. Fault-tolerant center problems with robustness and fairness. arXiv:2011.00817v2. Retrieved from https:\/\/arxiv.org\/abs\/2011.00817v2 (2020). Citation specific to version 2; latest version is a significantly different work."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2022.05.002"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(69)90017-2"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00056-7"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2854153"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5933"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39479-0_13"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/331499.331504"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1070-1"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977066.16"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FORC.2020.5"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00222-9"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00141-X"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1307.2520"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9883-7_4"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.02.004"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(99)00026-X"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/3524938.3525549"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0457-9"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90029-1"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18263-6_6"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2023.95"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1383369.1383382"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_70"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.03.005"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3799696","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T17:13:29Z","timestamp":1789146809000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3799696"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,9,11]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1145\/3799696"],"URL":"https:\/\/doi.org\/10.1145\/3799696","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,9,11]]},"assertion":[{"value":"2024-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-09-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}