Approximating the probabilistic p-Center problem under pressure

Marc Demange (), Marcel A. Haddad () and Cécile Murat ()
Additional contact information
Marc Demange: RMIT University
Marcel A. Haddad: Université Paris-Dauphine, PSL Research University
Cécile Murat: Université Paris-Dauphine, PSL Research University

Journal of Combinatorial Optimization, 2024, vol. 48, issue 1, No 9, 25 pages

Abstract: Abstract The Probabilistic p-Center problem under Pressure (Min P p CP) is a variant of the usual Min p-Center problem we recently introduced in the context of wildfire management. The problem is to locate p 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 Min P p CP-instance. Then, we propose some approximation results for Min P p CP. These results require approximation results for two variants of the (deterministic) Min p-Center problem called Min MAC p-Center and Min Partial p-Center.

Keywords: Variants of the p-Center problem; Shelter location under indeterminacy; Under pressure decision model; Probabilistic combinatorial optimization; Approximation algorithms (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01194-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:48:y:2024:i:1:d:10.1007_s10878-024-01194-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01194-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().