  The Probabilistic p-Center problem under Pressure (Min PpCP) is a variant of
the usual 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 to reach the closest accessible shelter in case of
fire. 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, for a given instance of Min
PpCP defined by an edge-weighted graph G=(V,E,L) and an integer p, we
characterize the set of feasible solutions of Min PpCP. We prove that Min PpCP
cannot be approximated with a ratio less than 56/55 on subgrids (subgraphs of
grids) of degree at most 3. Then, we propose some approximation results for Min
PpCP. 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.
