{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,13]],"date-time":"2025-12-13T07:13:12Z","timestamp":1765609992261},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T00:00:00Z","timestamp":1583884800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T00:00:00Z","timestamp":1583884800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s00453-020-00693-8","type":"journal-article","created":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T05:10:04Z","timestamp":1583903404000},"page":"2474-2501","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The Approximability of Multiple Facility Location on Directed Networks with Random Arc Failures"],"prefix":"10.1007","volume":"82","author":[{"given":"Refael","family":"Hassin","sequence":"first","affiliation":[]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[]},{"given":"F. Sibel","family":"Salman","sequence":"additional","affiliation":[]},{"given":"Danny","family":"Segev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,11]]},"reference":[{"issue":"3","key":"693_CR1","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"AA Ageev","year":"2004","unstructured":"Ageev, A.A., Sviridenko, M.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8(3), 307\u2013328 (2004)","journal-title":"J. Comb. Optim."},{"issue":"1\u20132","key":"693_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1\u20132), 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"693_CR3","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1109\/TR.1986.4335422","volume":"35","author":"MO Ball","year":"1986","unstructured":"Ball, M.O.: Computational complexity of network reliability analysis: an overview. IEEE Trans. Reliab. 35(3), 230\u2013239 (1986)","journal-title":"IEEE Trans. Reliab."},{"issue":"1","key":"693_CR4","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/S0304-3975(97)00124-2","volume":"209","author":"CJ Colbourn","year":"1998","unstructured":"Colbourn, C.J., Xue, G.: A linear time algorithm for computing the most reliable source on a series\u2013parallel graph with unreliable edges. Theor. Comput. Sci. 209(1), 331\u2013345 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"693_CR5","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.tcs.2009.08.003","volume":"412","author":"W Ding","year":"2011","unstructured":"Ding, W., Xue, G.: A linear time algorithm for computing a most reliable source on a tree network with faulty nodes. Theor. Comput. Sci. 412(3), 225\u2013232 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"693_CR6","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1002\/net.3230220303","volume":"22","author":"HA Eiselt","year":"1992","unstructured":"Eiselt, H.A., Gendreau, M., Laporte, G.: Location of facilities on a network subject to a single-edge failure. Networks 22(3), 231\u2013246 (1992)","journal-title":"Networks"},{"issue":"2","key":"693_CR7","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0020-0190(96)00024-5","volume":"58","author":"HA Eiselt","year":"1996","unstructured":"Eiselt, H.A., Gendreau, M., Laporte, G.: Optimal location of facilities on a network with an unreliable node or link. Inf. Process. Lett. 58(2), 71\u201374 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"693_CR8","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"693_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"key":"693_CR10","doi-asserted-by":"publisher","first-page":"199","DOI":"10.24033\/bsmf.545","volume":"24","author":"J Hadamard","year":"1896","unstructured":"Hadamard, J.: Sur la distribution des z\u00e9ros de la fonction $$\\zeta (s)$$ et ses cons\u00e9quences arithm\u00e9tiques. Bull. Soc. Math. Fr. 24, 199\u2013220 (1896)","journal-title":"Bull. Soc. Math. Fr."},{"issue":"3","key":"693_CR11","doi-asserted-by":"publisher","first-page":"931","DOI":"10.1007\/s10878-017-0121-5","volume":"34","author":"R Hassin","year":"2017","unstructured":"Hassin, R., Ravi, R., Salman, F.S.: Multiple facility location on a network with linear reliability order of edges. J. Comb. Optim. 34(3), 931\u2013955 (2017)","journal-title":"J. Comb. Optim."},{"issue":"301","key":"693_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"key":"693_CR13","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Springer, Berlin (1972)"},{"issue":"3","key":"693_CR14","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1002\/(SICI)1097-0037(199605)27:3<219::AID-NET7>3.0.CO;2-L","volume":"27","author":"E Melachrinoudis","year":"1996","unstructured":"Melachrinoudis, E., Helander, M.E.: A single facility location problem on a tree with unreliable edges. Networks 27(3), 219\u2013237 (1996)","journal-title":"Networks"},{"issue":"4","key":"693_CR15","first-page":"363","volume":"28","author":"LD Nel","year":"1990","unstructured":"Nel, L.D., Colbourn, C.J.: Locating a broadcast facility in an unreliable network. INFOR Inf. Syst. Oper. Res. 28(4), 363\u2013379 (1990)","journal-title":"INFOR Inf. Syst. Oper. Res."},{"issue":"1","key":"693_CR16","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions\u2014I. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"issue":"4","key":"693_CR17","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"JS Provan","year":"1983","unstructured":"Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12(4), 777\u2013788 (1983)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"693_CR18","doi-asserted-by":"publisher","first-page":"1437","DOI":"10.1016\/j.cor.2008.02.007","volume":"36","author":"J Santivanez","year":"2009","unstructured":"Santivanez, J., Melachrinoudis, E., Helander, M.E.: Network location of a reliable center using the most reliable route policy. Comput. Oper. Res. 36(5), 1437\u20131460 (2009)","journal-title":"Comput. Oper. Res."},{"key":"693_CR19","volume-title":"Calculus","author":"M Spivak","year":"1967","unstructured":"Spivak, M.: Calculus, 3rd edn. Cambridge University Press, Cambridge (1967)","edition":"3"},{"issue":"3","key":"693_CR20","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"key":"693_CR21","first-page":"183","volume":"20","author":"C Vall\u00e9e-Poussin","year":"1896","unstructured":"Vall\u00e9e-Poussin, C.: Recherches analytiques sur la th\u00e9orie des nombres premiers. Ann. Soc. Sci. Brux. 20, 183\u2013256 (1896)","journal-title":"Ann. Soc. Sci. Brux."},{"issue":"1","key":"693_CR22","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1002\/(SICI)1097-0037(199708)30:1<37::AID-NET5>3.0.CO;2-M","volume":"30","author":"G Xue","year":"1997","unstructured":"Xue, G.: Linear time algorithms for computing the most reliable source on an unreliable tree network. Networks 30(1), 37\u201345 (1997)","journal-title":"Networks"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00693-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00693-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00693-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T00:12:10Z","timestamp":1615421530000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00693-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,11]]},"references-count":22,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["693"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00693-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,11]]},"assertion":[{"value":"13 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}