{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T23:34:52Z","timestamp":1772580892979,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCR-9912422CCF-0430682DMI-0500263"],"award-info":[{"award-number":["CCR-9912422CCF-0430682DMI-0500263"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-9912422CCF-0430682DMI-0500263"],"award-info":[{"award-number":["CCR-9912422CCF-0430682DMI-0500263"]}],"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. Algorithms"],"published-print":{"date-parts":[[2008,8]]},"abstract":"\n We consider a fault-tolerant generalization of the classical uncapacitated facility location problem, where each client\n j<\/jats:italic>\n has a requirement that\n r<\/jats:italic>\n \n j<\/jats:italic>\n <\/jats:sub>\n distinct<\/jats:italic>\n facilities serve it, instead of just one. We give a 2.076-approximation algorithm for this problem using LP rounding, which is currently the best-known performance guarantee. Our algorithm exploits primal and dual complementary slackness conditions and is based on\n clustered randomized rounding<\/jats:italic>\n . A technical difficulty that we overcome is the presence of terms with negative coefficients in the dual objective function, which makes it difficult to bound the cost in terms of dual variables. For the case where all requirements are the same, we give a primal-dual 1.52-approximation algorithm.\n <\/jats:p>\n \n We also consider a fault-tolerant version of the\n k<\/jats:italic>\n -median problem. In the metric\n k<\/jats:italic>\n -median problem, we are given\n n<\/jats:italic>\n points in a metric space. We must select\n k<\/jats:italic>\n of these to be centers, and then assign each input point\n j<\/jats:italic>\n to the selected center that is closest to it. In the fault-tolerant version we want\n j<\/jats:italic>\n to be assigned to\n r<\/jats:italic>\n \n j<\/jats:italic>\n <\/jats:sub>\n distinct centers. The goal is to select the\n k<\/jats:italic>\n centers so as to minimize the sum of assignment costs. The primal-dual algorithm for fault-tolerant facility location with uniform requirements also yields a 4-approximation algorithm for the fault-tolerant\n k<\/jats:italic>\n -median problem for this case. This the first constant-factor approximation algorithm for the uniform requirements case.\n <\/jats:p>","DOI":"10.1145\/1383369.1383382","type":"journal-article","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T11:56:36Z","timestamp":1219838196000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":53,"title":["Fault-tolerant facility location"],"prefix":"10.1145","volume":"4","author":[{"given":"Chaitanya","family":"Swamy","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}]},{"given":"David B.","family":"Shmoys","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}]}],"member":"320","published-online":{"date-parts":[[2008,8,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038913.96607.c2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398594"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1882"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703405754"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00056-7"},{"key":"e_1_2_1_8_1","unstructured":"Hardy G. H. Littlewood J. E. and P\u00f3lya G. 1952. Inequalities. Cambridge University Press UK. Hardy G. H. Littlewood J. E. and P\u00f3lya G. 1952. Inequalities. Cambridge University Press UK."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510012"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of 4th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX). 177--183","author":"Jain K."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1100"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129787"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of 4th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX). 127--137","author":"Mahdian M."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435716"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383443"},{"key":"e_1_2_1_18_1","unstructured":"Mirchandani P. and Francis R. 1990. Discrete Location Theory. John Wiley New York. Mirchandani P. and Francis R. 1990. Discrete Location Theory. John Wiley New York."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258600"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/645591.659950"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 735--736","author":"Swamy C."},{"key":"e_1_2_1_22_1","unstructured":"Vazirani V. 2001. Approximation Algorithms. Springer NY. Vazirani V. 2001. Approximation Algorithms. Springer NY."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383382","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1383369.1383382","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:59Z","timestamp":1750255079000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383382"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1383369.1383382"],"URL":"https:\/\/doi.org\/10.1145\/1383369.1383382","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"2005-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}