{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T15:39:21Z","timestamp":1782833961886,"version":"3.54.5"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,9,21]],"date-time":"2016-09-21T00:00:00Z","timestamp":1474416000000},"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":[[2017,1,31]]},"abstract":"<jats:p>\n            In this article, we present improved inapproximability results for the\n            <jats:italic>k<\/jats:italic>\n            -level uncapacitated facility location problem. In particular, we show that there is no polynomial time approximation algorithm with performance guarantee better than 1.539 unless\n            <jats:italic>P<\/jats:italic>\n            =\n            <jats:italic>NP<\/jats:italic>\n            for the case when\n            <jats:italic>k<\/jats:italic>\n            = 2. For the case of general\n            <jats:italic>k<\/jats:italic>\n            (tending to infinity), we obtain a better hardness factor of 1.61.\n          <\/jats:p>\n          <jats:p>\n            Interestingly, our results show that the two-level problem is\n            <jats:italic>computationally harder<\/jats:italic>\n            than the well-known uncapacitated facility location problem (\n            <jats:italic>k<\/jats:italic>\n            = 1) since the best-known approximation guarantee for the latter problem is 1.488 due to Li [2013], and our inapproximability is a factor of 1.539 for the two-level problem. The only inapproximability result known before for this class of metric facility location problems is the bound of 1.463 due to Guha and Khuller [1999], which holds even for the case of\n            <jats:italic>k<\/jats:italic>\n            = 1.\n          <\/jats:p>","DOI":"10.1145\/2907050","type":"journal-article","created":{"date-parts":[[2016,9,21]],"date-time":"2016-09-21T13:13:56Z","timestamp":1474463636000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Inapproximability of the Multilevel Uncapacitated Facility Location Problem"],"prefix":"10.1145","volume":"13","author":[{"given":"Ravishankar","family":"Krishnaswamy","sequence":"first","affiliation":[{"name":"Microsoft Research India, Bangalore, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maxim","family":"Sviridenko","sequence":"additional","affiliation":[{"name":"Yahoo Labs, NYC, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,9,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00144-1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.8.3.289"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00162-1"},{"key":"e_1_2_1_4_1","volume-title":"In: R","author":"Ageev A.","year":"1990"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102417215"},{"key":"e_1_2_1_6_1","unstructured":"A. Archer. 2000. Inapproximability of the asymmetric facility location and k-median problems. Unpublished manuscript.  A. Archer. 2000. Inapproximability of the asymmetric facility location and k-median problems. Unpublished manuscript."},{"key":"e_1_2_1_7_1","volume-title":"Combinatorial Optimization, 3","author":"Barros A."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"A.\n      Bumb\n     and \n      W.\n      Kern\n  . \n  2001\n  . A simple dual ascent algorithm for the multilevel facility location problem. Approximation randomization and combinatorial optimization (Berkeley CA 2001) 55--62 Lecture Notes in Comput\n  . Sci. 2129 Springer Berlin.   A. Bumb and W. Kern. 2001. A simple dual ascent algorithm for the multilevel facility location problem. Approximation randomization and combinatorial optimization (Berkeley CA 2001) 55--62 Lecture Notes in Comput. Sci. 2129 Springer Berlin.","DOI":"10.1007\/3-540-44666-4_10"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/070708901"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9575-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398594"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703405754"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Z. Drezner and H. W. Hamacher. 2002. Facility location - applications and theory. Springer.  Z. Drezner and H. W. Hamacher. 2002. Facility location - applications and theory. Springer.","DOI":"10.1007\/978-3-642-56082-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.11.007"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998)","author":"Guha S."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1977.104"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(83)90181-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.01.007"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"M. Mahdian Y. Ye and J. Zhang. 2002. Improved approximation algorithms for metric facility location problems. In K. Jansen S. Leonardi and V. V. Vazirani (Eds.). APPROX. Springer 229--242.   M. Mahdian Y. Ye and J. Zhang. 2002. Improved approximation algorithms for metric facility location problems. In K. Jansen S. Leonardi and V. V. Vazirani (Eds.). APPROX. Springer 229--242.","DOI":"10.1007\/3-540-45753-4_20"},{"key":"e_1_2_1_26_1","volume-title":"Francis","author":"Mirchandani Pitu B.","year":"1990"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a007"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258600"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Symposium on Applied Mathematics, 61","author":"Shmoys D.","year":"2004"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/645591.659950"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721853"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90258-3"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.28.10.1091"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3112681.3113166"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2907050","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2907050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:25Z","timestamp":1750222465000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2907050"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,21]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1,31]]}},"alternative-id":["10.1145\/2907050"],"URL":"https:\/\/doi.org\/10.1145\/2907050","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,21]]},"assertion":[{"value":"2013-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}