{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:41Z","timestamp":1740122441741,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T00:00:00Z","timestamp":1722470400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T00:00:00Z","timestamp":1722988800000},"content-version":"vor","delay-in-days":6,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010665","name":"H2020 Marie Sk\u0142odowska-Curie Actions","doi-asserted-by":"publisher","award":["691161"],"award-info":[{"award-number":["691161"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Royal Melbourne Institute of Technology"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Probabilistic <jats:italic>p<\/jats:italic>-Center problem under Pressure (<jats:italic>p<\/jats:italic>) is a variant of the usual <jats:italic>p<\/jats:italic> problem we recently introduced in the context of wildfire management. The problem is to locate <jats:italic>p<\/jats:italic> shelters minimizing the maximum distance people will have to cover in case of fire in order to reach the closest accessible shelter. The landscape is divided into zones and is modeled as an edge-weighted graph with vertices corresponding to zones and edges corresponding to direct connections between two adjacent zones. The risk associated with fire outbreaks is modeled using a finite set of fire scenarios. Each scenario corresponds to a fire outbreak on a single zone (i.e., on a vertex) with the main consequence of modifying evacuation paths in two ways. First, an evacuation path cannot pass through the vertex on fire. Second, the fact that someone close to the fire may not take rational decisions when selecting a direction to escape is modeled using new kinds of evacuation paths. In this paper, we characterize the set of feasible solutions of <jats:italic>p<\/jats:italic>-instance. Then, we propose some approximation results for <jats:italic>p<\/jats:italic>. These results require approximation results for two variants of the (deterministic) <jats:italic>p<\/jats:italic> problem called <jats:italic>p<\/jats:italic> and <jats:italic>p<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s10878-024-01194-y","type":"journal-article","created":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T11:07:15Z","timestamp":1723028835000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating the probabilistic p-Center problem under pressure"],"prefix":"10.1007","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6195-2919","authenticated-orcid":false,"given":"Marc","family":"Demange","sequence":"first","affiliation":[]},{"given":"Marcel A.","family":"Haddad","sequence":"additional","affiliation":[]},{"given":"C\u00e9cile","family":"Murat","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,7]]},"reference":[{"key":"1194_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and approximation: combinatorial optimization problems and their approximability properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello G, Protasi M, Marchetti-Spaccamela A, Gambosi G, Crescenzi P, Kann V (1999) Complexity and approximation: combinatorial optimization problems and their approximability properties, 1st edn. Springer-Verlag, New York Inc, Secaucus, NJ","edition":"1"},{"issue":"3","key":"1194_CR2","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1016\/S0166-218X(02)00384-0","volume":"127","author":"I Averbakh","year":"2003","unstructured":"Averbakh I (2003) Complexity of robust single facility location problems on networks with uncertain edge lengths. Discret Appl Math 127(3):505\u2013522","journal-title":"Discret Appl Math"},{"issue":"4","key":"1194_CR3","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/S0966-8349(98)00033-3","volume":"5","author":"I Averbakh","year":"1997","unstructured":"Averbakh I, Berman O (1997) Minimax regret p-center location on a network with demand uncertainty. Locat Sci 5(4):247\u2013254","journal-title":"Locat Sci"},{"issue":"3","key":"1194_CR4","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1051\/ro\/2017046","volume":"52","author":"V Bayram","year":"2018","unstructured":"Bayram V, Yaman H (2018) A stochastic programming approach for shelter location and evacuation planning. RAIRO-Oper Res 52(3):779\u2013805","journal-title":"RAIRO-Oper Res"},{"key":"1194_CR5","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/978-3-319-13111-5_4","volume-title":"Location science","author":"H Calik","year":"2015","unstructured":"Calik H, Labb\u00e9 M, Yaman H (2015) p-Center problems. In: Laporte G, Nickel S, Saldanha da Gama F (eds) Location science. Springer International Publishing, Cham, pp 79\u201392"},{"issue":"1","key":"1194_CR6","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.seps.2011.04.004","volume":"46","author":"AM Caunhye","year":"2012","unstructured":"Caunhye AM, Nie X, Pokharel S (2012) Optimization models in emergency logistics: a literature review. Socio-economic Plann Sci 46(1):4\u201313","journal-title":"Socio-economic Plann Sci"},{"issue":"3","key":"1194_CR7","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0020-0190(97)00224-X","volume":"65","author":"S Chaudhuri","year":"1998","unstructured":"Chaudhuri S, Garg N, Ravi R (1998) The p-neighbor k-center problem. Inf Process Lett 65(3):131\u2013134","journal-title":"Inf Process Lett"},{"issue":"1","key":"1194_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark BN, Colbourn CJ, Johnson DS (1990) Unit disk graphs. Discret Math 86(1):165\u2013177","journal-title":"Discret Math"},{"key":"1194_CR9","doi-asserted-by":"crossref","unstructured":"Correia I, da\u00a0Gama FS (2015) Facility location under uncertainty. In: Location science. Springer, pp\u00a0177\u2013203","DOI":"10.1007\/978-3-319-13111-5_8"},{"issue":"1","key":"1194_CR10","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1111\/gean.1999.31.1.217","volume":"31","author":"MS Daskin","year":"1999","unstructured":"Daskin MS, Owen SH (1999) Two new location covering problems: the partial p-Center problem and the partial set covering problem. Geogr Anal 31(1):217\u2013223","journal-title":"Geogr Anal"},{"issue":"2","key":"1194_CR11","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s13675-020-00124-x","volume":"8","author":"M Demange","year":"2020","unstructured":"Demange M, Gabrel V, Haddad MA, Murat C et al (2020) A robust p-center problem under pressure to locate shelters in wildfire context. EURO J Comput Optim 8(2):103\u2013139","journal-title":"EURO J Comput Optim"},{"key":"1194_CR12","unstructured":"Demange M, Haddad MA, Murat C (2018) The probabilistic k-Center problem. In: Proceedings of the GEOSAFE workshop on robust solutions for fire fighting (L\u2019Aquila, Italy), pp\u00a062\u201374"},{"key":"1194_CR13","unstructured":"Diestel, R (2018) Graph theory. Springer"},{"key":"1194_CR14","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.apm.2019.07.025","volume":"77","author":"B Du","year":"2020","unstructured":"Du B, Zhou H, Leus R (2020) A two-stage robust model for a reliable p-Center facility location problem. Appl Math Model 77:99\u2013114","journal-title":"Appl Math Model"},{"key":"1194_CR15","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness (series of books in the mathematical sciences), 1st edn. In: Freeman WH"},{"issue":"2","key":"1194_CR16","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum DS, Shmoys DB (1985) A best possible heuristic for the k-center problem. Math Oper Res 10(2):180\u2013184","journal-title":"Math Oper Res"},{"issue":"3","key":"1194_CR17","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"DS Hochbaum","year":"1986","unstructured":"Hochbaum DS, Shmoys DB (1986) A unified approach to approximation algorithms for bottleneck problems. J ACM 33(3):533\u2013550","journal-title":"J ACM"},{"issue":"3","key":"1194_CR18","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0166-218X(79)90044-1","volume":"1","author":"W-L Hsu","year":"1979","unstructured":"Hsu W-L, Nemhauser GL (1979) Easy and hard bottleneck location problems. Discret Appl Math 1(3):209\u2013215","journal-title":"Discret Appl Math"},{"issue":"1","key":"1194_CR19","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10479-010-0736-8","volume":"181","author":"R Huang","year":"2010","unstructured":"Huang R, Kim S, Menezes MB (2010) Facility location for large-scale emergencies. Ann Oper Res 181(1):271\u2013286","journal-title":"Ann Oper Res"},{"issue":"3","key":"1194_CR20","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/0137040","volume":"37","author":"O Kariv","year":"1979","unstructured":"Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. I: The $$p$$-centers. SIAM J Appl Math 37(3):513\u2013538","journal-title":"SIAM J Appl Math"},{"key":"1194_CR21","doi-asserted-by":"crossref","unstructured":"Laporte G, Nickel S, da\u00a0Gama FS (2015) Location science, vol.\u00a0528. Springer","DOI":"10.1007\/978-3-319-13111-5"},{"issue":"1","key":"1194_CR22","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.ejor.2013.03.028","volume":"230","author":"C Lu","year":"2013","unstructured":"Lu C (2013) Robust weighted vertex p-center model considering uncertain data: an application to emergency management. Eur J Oper Res 230(1):113\u2013121","journal-title":"Eur J Oper Res"},{"issue":"2","key":"1194_CR23","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1016\/j.ejor.2017.03.043","volume":"262","author":"LI Mart\u00ednez-Merino","year":"2017","unstructured":"Mart\u00ednez-Merino LI, Albareda-Sambola M, Rodr\u00edguez-Ch\u00eda AM (2017) The probabilistic p-Center problem: planning service for potential customers. Eur J Oper Res 262(2):509\u2013520","journal-title":"Eur J Oper Res"},{"issue":"7","key":"1194_CR24","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1080\/07408170500216480","volume":"38","author":"LV Snyder","year":"2006","unstructured":"Snyder LV (2006) Facility location under uncertainty: a review. IIE Trans 38(7):547\u2013564","journal-title":"IIE Trans"},{"issue":"1","key":"1194_CR25","first-page":"48","volume":"6","author":"M Taghavi","year":"2012","unstructured":"Taghavi M, Shavandi H (2012) The p-Center problem under uncertainty. J Ind Syst Eng 6(1):48\u201357","journal-title":"J Ind Syst Eng"},{"issue":"2","key":"1194_CR26","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan R (1972) Depth-first search and linear graph algorithms. SIAM J Comput 1(2):146\u2013160","journal-title":"SIAM J Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01194-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01194-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01194-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T19:10:55Z","timestamp":1724440255000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01194-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["1194"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01194-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,8]]},"assertion":[{"value":"13 July 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"9"}}