Marc Demange
email: marc.demange@rmit.edu.au

Marcel Adonis Haddad
email: marcel-adonis.haddad@dauphine.eu

Cécile Murat
email: cecile.murat@lamsade.dauphine.fr

The probabilistic k-center problem

published or not. The documents may come

Introduction

Forest fires are becoming an increasing concern for the population across the globe, and with projected climate change, this upward trend seems set to continue. Operations Research methods are one of the tools used by wildfire managers to guide decision making [START_REF] Martell | A review of recent forest and wildland fire management decision support systems research[END_REF][START_REF] Minas | A review of operations research methods applicable to wildfire management[END_REF]. Evacuation planning and facility location under uncertainty are some of the considered problems. In this paper, we address the problem of locating a number k of emergency gathering points in a forest, in anticipation of fires. The general objective is to minimize the risk of having people trapped by the flames, i.e., maximize their chance to reach a safe gathering point or shelter before the fire arrives. Rescue operations are deployed to evacuate people from the shelters but these shelters are also equipped to protect people against flames if rescue cannot be completed on-time.

In our model, the landscape is represented by an adjacency graph G = (V, E). Each node corresponds to an area and two nodes are connected by an edge if the related areas are adjacent. A fire may ignite on a node and then can spread on all neighboring nodes at a fixed maximum distance called the range of impact. The impacted zone is then the set of vertices where the fire spreads. In a real case scenario, the fire can spread over very large areas and the impacted zone grows dynamically. However, it might be relevant to focus on a relatively short period after ignition or after the alert, seen as the time required for all people present in the area to reach an assembly point. This motivates us to consider small ranges of impact depending on the efficiency of the early warning system. We then assume that people are safe after reaching the assembly point; this hypothesis is relevant depending on the exact nature and design of the assembly points.

Our problem is a particular case of location-allocation problems. A solution describes not only the location of emergency assembly points, defined as a subset K ⊆ V, |K| = k and known as a k-center (location problem), but it also includes a strategy people should follow in case of fire to reach one assembly point (evacuation process). The location can be addressed during the preparedness phase and may involve sophisticated solutions. The allocation however is mainly addressed during the response phase, which usually requires efficient and simple processes. Indeed, even though evacuation scenarios can be prepared in advance, they should remain straightforward in order to be followed by untrained people, without supervision and under high stress conditions. Here, we will consider that somebody is assigned to the closest assembly point with the constraint he/she will never go through the fire; this constraint will be precise later. For a real case implementation, this could be supported by simple early warning system deployed on site and indicating the direction and distance of the closest accessible shelter(s). The objective is then to minimize the maximum distance from each vertex v to K, called the radius of the kcenter K. It corresponds to the worst case situation for someone present in the risk zone when a fire starts. However high uncertainty lies on where a fire ignites and thus on the accessibility of some vertices or on the practicability of some paths during the event. We model it as different possible scenarios, where a scenario is given by an ignition vertex and a range of impact. Then, the objective becomes the expected value of the radius in the new instance. We will restrict ourselves to a simple fire outbreak scenarios. This hypothesis is supported by our choice to focus on a relative short period after ignition. To simplify the problem in this first study we will consider a fixed range of impact. This corresponds to the situation where the considered region is homogeneous in terms of topography, wind and fuel load conditions.

The framework of Probabilistic combinatorial optimization [START_REF] Bertsimas | Probabilistic combinatorial optimization problems[END_REF][START_REF] Jaillet | Probabilistic traveling salesman problems[END_REF][START_REF] Murat | Probabilistic combinatorial optimization on graphs[END_REF], also known as a priori optimization, is particularly suitable to model such situations, where one has to deal with destructions or obstructions on a usual set-up that make an original global strategy potentially unfeasible. In this approach, a problem is decomposed in two phases. The whole instance is considered during the first phase (seen as the preparedness phase), while in a second time (response phase) only a part of the infrastructure remains available after an uncertain event has occurred. A modification strategy is identified beforehand to "automatically" transform a solution on the whole instance (called an a priori solution) to a feasible solution on a partial available instance (an a posteriori solution). To represent uncertainty, probabilities are assigned to the different possible partial instances. More precisely it is usually based on a probability distribution on the different components of the initial instance representing how likely they could be affected. The objective is then to compute an a priori solution on the whole instance optimizing the expected value of the effective solution induced on the partial instance using the modification scheme. Given our allocation strategy that assigns a person at risk to the closest safety point, the modification scheme describes the new set of emergency points after the event and the new possible routes so as to recompute the new allocation and the corresponding objective value. In this paper, since we assume the emergency gathering points or shelters are safe and since it is not possible to define new locations during the response phase, we consider that the k-center is not modified. Indeed, any original k-center always remains feasible in the new graph. The modification scheme only corresponds to the new possible routes; roughly speaking these routes are paths that do not cross the impacted zone. Specific rules are considered for people in this impacted zone as detailed in the next section.

In the usual non-probabilistic case, also called deterministic case, our problem is known as the Minimum k-Center problem and to our knowledge this is the first time the Probabilistic k-center is defined and discussed [START_REF] Calik | p-Center Problems[END_REF]. However, restricted versions of routing and networking-design probabilistic minimization problems (in complete graphs) have been studied (see, e.g., [START_REF] Averbakh | Probabilistic a priori routing-location problems[END_REF][START_REF] Bertsimas | Traveling salesman facility location problems[END_REF][START_REF] Bertsimas | The probabilistic minimum spanning tree problem[END_REF][START_REF] Jaillet | Shortest path problems with node failures[END_REF][START_REF] Jaillet | The probabilistic vehicle routing problem[END_REF] ). In [START_REF] Balaprakash | Estimation-based metaheuristics for the probabilistic traveling salesman problem[END_REF][START_REF] Bianchi | Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms[END_REF][START_REF] Birattari | Estimation-based local search for stochastic combinatorial optimization using delta evaluations: a case study on the probabilistic traveling salesman problem[END_REF][START_REF] Campbell | Aggregation for the probabilistic traveling salesman problem[END_REF], the analysis of the probabilistic minimum traveling salesman problem, originally presented in [START_REF] Bertsimas | Probabilistic combinatorial optimization problems[END_REF][START_REF] Jaillet | Probabilistic traveling salesman problems[END_REF], has been revisited in order to propose new efficient resolution. Several other combinatorial problems have been also handled in the probabilistic combinatorial optimization approach, with or without recourse, including minimum vertex cover and maximum independent set [START_REF] Murat | A priori optimization for the probabilistic maximum independent set problem[END_REF][START_REF] Murat | The probabilistic minimum vertex-covering problem[END_REF], longest path [START_REF] Murat | The probabilistic longest path problem[END_REF], Steiner tree problems [START_REF] Paschos | Steiner forests on stochastic metric graphs[END_REF][START_REF] Paschos | Probabilistic models for the steiner tree problem[END_REF], minimum spanning tree [START_REF] Bertsimas | The probabilistic minimum spanning tree problem[END_REF][START_REF] Boria | On the probabilistic min spanning tree problem[END_REF], minimum dominating set [START_REF] Boria | The probabilistic minimum dominating set problem[END_REF] and some other general combinatorial graph problems [START_REF] Murat | Probabilistic optimization in graph-problems[END_REF].

In this paper we apply the probabilistic combinatorial optimization setting for the k-center problem and we use the following notations. Let G = (V, E) be an undirected and connected graph with V = {0, . . . , n}. For v ∈ V , N (v) is the set of its neighbors. A path of length m is a sequence v 0 , . . . , v m of pairwise distinct vertices where ∀i ∈ {0, . . . , m -1}, v i v i+1 ∈ E. For x, y ∈ V , we denote by δ(x, y) the distance between x and y (that is the length of the shortest path between them). Similarly for a set

K ⊆ V , δ(x, K) = min y∈K δ(x, y). Given a k-center K ⊆ V, |K| = k, its radius in G is denoted by r K = max v∈V δ(v, K).
Finally, given a real-valued function f with domain A, we denote arg min

x∈A f (x) the set {x ∈ A : f (x) = min y∈A f (y)} of the minimum(s) of f in A.
The paper is organized as follows. In Section 2, we introduce and define the problem, namely Probabilistic k-Center. In Section 3, we give and prove an explicit optimal solution on path and cycle instances. Section 4 deals with hardness of approximation on planar graphs of degrees 2 or 3. Finally, we conclude in Section 5.

Definition of the problem

Probabilistic k-Center is characterized by a couple (S, M), where S is the set of scenarios in each instance, and M is a modification strategy. In this paper we study scenarios where the fire is limited to a simple node. Then S = {s i : i ∈ V } with s i the scenario where vertex i burns. With the considered modification strategy M 0 , the location of the centers are conserved and the vertices are affected to the nearest center in the available instance. This strategy involves the following: when a fire ignites, all the people in the forest try to escape to the closest shelter to get evacuated by the rescue. If there is a shelter in the ignition area, we assume that people in this area find refuge in that shelter. Otherwise the people in the ignition zone always flee in the opposite direction of the fire. Once at sufficient distance, they can choose their path rationally in order to get to the closest shelter.

An instance of our problem is then a couple (G,P) with G a graph and P a probability system associated with the vertices. It gives, for each vertex, the probability of fire on it. By default, we will consider a uniform distribution under the assumption that we have one fire outbreak at a time on a simple node. So, each scenario has probability p = 1 |V | . So in this work, Probabilistic k-Center will refer to this set-up. For scenario s j and for any x, y ∈ V , we denote by δ j (x, y) the distance between x and y in G \ {j}. Note that δ j (x, x) = 0 and δ j (x, y) = +∞ if there is no path between x and y. Then, for scenario s j and K ⊂ V , the induced evacuation distance of a node x is given by:

D j (x, K) = δ j (x, K) if (x = j) or if (x = j and j ∈ K) max x∈N (j) {1 + min y∈K δ j (x, y)} if x = j and j ∈ K (1)
Then, the disrupted radius of K for scenario s j induced by M 0 is:

r K j = max x∈V D j (x, K) (2)
We illustrate these definitions for k = 3 on a path of nine vertices and the 3-center K = {0, 5, 8}, whose nodes are drawn as pentagons. Figure 1, gives, for each node x, the value of δ(x, K). So, the radius of this solution is 2. In Figure 2, we illustrate a fire occurring on node 1. We give under each node x ∈ V the value of D 1 (x, K), and

0 1 2 2 1 0 1 1 0 0 1 2 3 4 5 6 7 8
Figure 1: The distance of each node to the 3-centers {0,5,8} in the deterministic case.

underline it when it has changed. For example, node 2 is affected since the original evacuation path to shelter 0 is no more operational. Note that, in the worst case, people on node 1 escape to node 2 and then to shelter 5. The disrupted radius r K 1 of scenario 1 is 4.

0 4 3 2 1 0 1 1 0 0 1 2 3 4 5 6 7 8
Figure 2: Evacuation distances in the scenario s 1 .

Figure 3 illustrates a fire on node 5, with a shelter. It affects nodes 3,4 and 6.

We denote by E the objective function of the Probabilistic k-Center problem. It is the expectation value of the disrupted radius of K :

E(K) = j∈V pr K j = p • j∈V r K j (3)
A solution K is said feasible if its objective value is finite. We denote by K(G) the set of feasible solutions.

Remark 1. Denote by Ψ(G) the set of connected components of a graph G. Then K is a feasible solution if ∀j ∈ V, ∀W ∈ Ψ(V \ {j}), K ∩ W = ∅.
An optimal solution for our version of the Probabilistic k-Center problem is then a k-center K * verifying K * ∈ arg min K∈K {E(K)}.

We introduce the following decomposition of the objective function:

E(K) = E s (K) + E s(K ) s.t. : E s (K) = p j∈K r K j , E s(K ) = p j∈G\K r K j (4)
In other words, E s (K) is the contribution of scenarios for which fires occur in K (called the skeleton), and E s(K ) is the contribution of scenarios for which fires occur on the other vertices (called the body). We can treat these components as two different problems. In particular, E s(K ) corresponds to a version of our problem where the nodes of K are fortified [START_REF] Church | Protecting critical assets: the r-interdiction median problem with fortification[END_REF], which means they are immune to fire. Note that, if a solution is optimal for both components, then it is optimal for the whole problem.

Moreover, we propose another evaluation function, denoted E, corresponding to the expected evacuation distance in the local area of the ignition node j defined as the close neighborhood (N (j) ∪ {j}) of j. The locally induced radius is then denoted r K j = max x∈N (j)∪{j} D j (x, K) :

E(K) = p • j∈V r K j (5)
Obviously, for a feasible K and ∀j ∈ V , we have:

E(K) ≤ E(K) (6)
We similarly decompose E(K) in E s (K) and E s(K ).

An explicit solution on Paths and Cycles

Denote P n+1 a path on n + 1 vertices, C n a cycle on n vertices, and H a graph that is either a path or cycle with n edges. Given the feasibility condition seen in Remark 1, for K = (v 1 , . . . , v k ) ∈ K(P n+1 ), we necessarily have v 1 = 0 and v k = n. Thus, K induces k -1 segments µ i of length λ i , i = 1, . . . , k -1. On a cycle C n and for K ∈ K(C n ), K would induces k segments. In the following we deal with path and cycles simultaneously, unless specified otherwise. We define κ = k if H is a cycle, and κ = k -1 if H is a path. We denote E H (K) the value of the solution K in H. Denoting λ = (λ 1 , . . . , λ κ ), we can consider equivalently E H (K), E H s (K) and E H s (K) as functions of λ(K). We say that λ = (λ 1 , . . . , λ κ ) is not decreasing if λ 1 ≤ . . . ≤ λ κ . We define λ ≤ = (λ i1 , . . . , λ iκ ), where i : {1, . . . , κ} → {1, . . . , κ} is a permutation such that λ i1 ≤ . . . ≤ λ iκ , a non decreasing solution induced by λ. The possible λs corresponding to a feasible k-center are all vectors, (λ 1 , . . . , λ κ ) ∈ N κ such that κ i=1 λ i = n. We denote by Λ(H) their set. The aim of this section is to give an explicit optimal solution for Probabilistic k-Center on paths and cycles. In both cases, the balanced solution (see Definition 1), optimal in the deterministic case, reveals also to be optimal in the probabilistic case. However, the proof is non-trivial. For paths, we will show, in a first step, that this solution minimizes the contribution of the skeleton and in a second step, that it minimizes also the contribution of the body. We then derive the case on cycle by a reduction to the case on paths.

Expression of the disrupted radius and balanced solution

The results in this subsection hold for both cycles and paths with n edges. We define µ 0 = µ κ+1 = ∅ in the case of paths. We recall that the objective function of the Probabilistic k-Center problem requires the disrupted radius of K induced for each scenario (see Equations ( 2), ( 3)). For scenario s j , let µ i be a segment such that j ∈ µ i , i ∈ {1, . . . , κ}. We have:

r K j = max{max x∈µi {D j (x, K)}, max x∈H\µi {D j (x, K)}}
Observe that, ∀x ∈ H \ µ i , the evacuation path is not modified. On µ q ∈ µ i , the evacuation path of any node is shorter than the evacuation path of the middle node(s) of µ q . Then, ∀x ∈ µ q , D j (x, K) ≤ µ i is always shorter than one of the evacuation paths from j or -if j ∈ K -from one of his neighbor. We distinguish then two cases:

If j ∈ K, max x∈µi∪µi+1 {D j (x, K)} = max{D j (j -1, K), D j (j + 1, K), } since D j (j, K) = 0. Based on Equation (1)
we obtain:

r K j = max{λ i -1, λ i+1 -1, max q=1,...,κ;j ∈µq λq 2 } (7)
For example, in Figure 3, If

r K 5 = max{λ 1 -1, λ 2 -1, λ3 2 } = max{4
j ∈ K, max x∈µi {D j (x, K)} = D j (j, K). Using Equation (1) we then have D j (j, K) = max{j -v i , v i+1 -j},
and therefore:

r K j = max{j -v i , v i+1 -j, max q=1,...,κ;j ∈µq λq 2 } (8) Definition 1. A solution is called balanced if ∀i, j ∈ {1, . . . , κ}, |λ i -λ j | ≤ 1
, and it will be called non-decreasing if ∀i, j ∈ {1, . . . , κ}, i < j, λ i ≤ λ j . We denote K B ∈ K(H) the solution such that K B is a non-decreasing balanced k-center.

We denote by λ B the related vector of distances. Thus, we have

λ B i ∈ { n κ , n κ } and λ B 1 ≤ . . . ≤ λ B κ for i = 1, . . . , κ.
In what follows, we show that the Probabilistic k-Center problem has an optimal balanced solution on paths and cycles. For k ≥ n 2 , we have the following result (the proof is given in Appendix):

Proposition 1. For k ≥ n 2 , K B is an optimum solution for Probabilistic k-Center on paths and cycles.

So, in what follows, we assume k < n 2 . In this case, we show in Appendix the Lemma 1 :

Lemma 1. E H s (λ B ) = E H s (λ B ) , E H s (λ B ) = E H s (λ B ) and E H (λ B ) = E H (λ B ).
In subsection 3.2, we show that K B minimizes E Pn+1 s (K). In order to prove that K B minimizes also E Pn+1 s (K), in subsection 3.3, we establish a more general result, by showing that K B minimizes E H s (K). So, we can obtain Theorem 1 for paths and in subsection 3.4, we consider cycles.

The skeleton part on paths

In this subsection, we focus on the skeleton part on paths. We first show that some balanced solution minimizes E Pn+1 s (K) and then, that it minimizes as well E Pn+1 s (K). Based on Equations ( 5), ( 4) and [START_REF] Averbakh | Probabilistic a priori routing-location problems[END_REF] we have:

E Pn+1 s (λ) = p • λ 1 + κ i=2 max(λ i-1 , λ i ) + λ κ -p(κ + 1) (9) Lemma 2. E Pn+1 s (λ) ≥ E Pn+1 s (λ ≤ )
Proof. Consider λ = (λ 1 , . . . λ κ ) with λ i ≥ 0, i = 1, . . . , κ. If λ 1 = max{λ i , i = 1, . . . κ}, we define r = 0, else let r be the maximum index in {1, . . . , κ} such that λ 1 ≤ . . . ≤ λ r and ∀j ≥ r, λ j ≥ λ r . If r = κ, we have λ = λ ≤ and nothing needs to be shown. Else, r < κ -1 (the value r = κ -1 is not possible), we consider s ∈ arg min{λ j , j = r + 1, . . . , κ}: by definition, we have λ r+1 ≥ λ r if r > 0, s > r + 1 and λ r ≤ λ s < λ r+1 . We then consider λ the vector obtained from λ by moving the s th coordinate at the position r + 1:

λ i = λ i , i = 1, . . . , r λ r+1 = λ s , λ i = λ i-1 , i = r + 2, . . . , s λ i = λ i , i > s We claim that E Pn+1 s (λ ) ≤ E Pn+1 s
(λ). Indeed, suppose first s < κ and consider the expression of E Pn+1 s (λ ) and E Pn+1 s (λ), as sums of κ + 1 terms (see Equation ( 9)). The three terms max(λ r , λ r+1 ), max(λ s-1 , λ s ) and max(λ s , λ s+1 ) in the expression of E Pn+1 s (λ) are replaced in the expression of E Pn+1 s (λ ) by max(λ r , λ s ), max(λ s , λ r+1 ) and max(λ s-1 , λ s+1 ) and all the other terms are identical in both expressions. We conclude:

E Pn+1 s (λ) -E Pn+1 s (λ ) = p (max(λ r , λ r+1 ) + max(λ s-1 , λ s ) + max(λ s , λ s+1 ) -[max(λ r , λ s ) + max(λ s , λ r+1 ) + max(λ s-1 , λ s+1 )]) = p (λ r+1 + λ s-1 + λ s+1 -λ s -λ r+1 -max(λ s-1 , λ s+1 ))) = p (λ s-1 + λ s+1 -λ s -max(λ s-1 , λ s+1 )) ≥ 0
where the last inequality holds since λ s ≤ min(λ s-1 , λ s+1 ). Suppose now s = κ, then a similar approach without the terms involving s + 1 leads to:

E Pn+1 s (λ) -E Pn+1 s (λ ) = p (max(λ r , λ r+1 ) + max(λ κ-1 , λ κ ) -[max(λ r , λ κ ) + max(λ κ , λ r+1 )]) = p (λ r+1 + λ κ-1 -λ κ -λ r+1 ) ≥ 0 (since λ κ-1 ≥ λ κ )
Note that these arguments hold also if r = 0. The proposition is deduced by induction, repeatedly replacing the current vector λ by λ .

We are now ready to show the main result of this part:

Proposition 2. λ B ∈ arg min{E Pn+1 s (λ), λ ∈ Λ(P n+1 )}. Proof. First we claim that λ B ∈ arg min{ E Pn+1 s (λ), λ ∈ Λ(P n+1 )}. Indeed in order to minimize E Pn+1 s (λ) for λ ∈ Λ(P n+1
), Lemma 2 ensures we can restrict ourselves to non decreasing solutions. But for any non decreasing λ in Λ(P n+1 ), we have E Pn+1 s (λ) = p(n+λ κ )-p(κ+1) (Equation ( 9)) and consequently a non decreasing solution minimizing E Pn+1 s (λ) is obtained by solving:

       min λ κ λ 1 ≤ . . . ≤ λ κ κ i=1 λ i = n, λ ∈ N κ
This admits λ B as unique solution. Therefore, by Lemma 1 and Equation ( 6), we have:

E Pn+1 s (λ B ) = E Pn+1 s (λ B ) = min λ∈Λ(Pn+1) E Pn+1 s (λ) ≤ min λ∈Λ(Pn+1) E Pn+1 s (λ) and consequently λ B ∈ arg min{E Pn+1 s (λ), λ ∈ Λ(P n+1 )}.

The body part

Here, we focus on ignition outside the skeleton, the "body" part, on paths and cycles and show that there is a balanced solution minimizing E H s (K). Our proof for the body part immediately applies for both cases, which is worth to be noted since, as already mentioned, the problem restricted to the body has its own interest in applications. First, we highlight some properties of a balanced solution. For the following let us denote K = (v 1 , . . . , v k ). Then E H s (λ) = p i=1,...,κ α(λ i ). Denote also A a logical proposition, and by 1 A the boolean function such that

1 A = 1 if A is true, and 1 A = 0 if A is false. For j ∈ λ 1 , we have α(λ a ) = j∈µ1\K max{j -v a , v a+1 -j} = j∈µa\K max{j, λ a -j} = 2 • λa-1 j= λa 2 (j) -1 (λa even) ( λa 2 ) = λa 2 (λ a + λa 2 -1) -1 (λa even) ( λa 2
). The previous result applies also to α(λ b ). As λ b = m -λ a , we can express α(λ a ) + α(λ b ) as a function of λ a :

α(λ a ) + α(λ b ) = λa 2 (λ a + λa 2 -1) -1 (λa even) ( λa 2 ) + m-λa 2 (m -λ a + m-λa 2 -1) -1 ((m-λa) even) ( m-λa 2 )
If we study the different combinations of parities of λ a and m, we get:

3 2 λ 2 a -3n 2 λ a + 3 4 m 2 -m ≤ α(λ a ) + α(λ b ) ≤ 3 2 λ 2 a -3m 2 λ a + 3 4 m 2 -m + 1 2
Defining the function f (λ a ) = 3 2 λ 2 a -3m 2 λ a , we have:

α(λ a ) + α(λ b ) - 1 2 ≤ f (λ a ) + 3 4 m 2 -m ≤ α(λ a ) + α(λ b ) (10)
and the same holds for (λ a , λ b ). 3 4 m 2 -m is fixed and f (λ a ) increases for λ a > m 2 . Since λ a ≤ λ a , f (λ a ) ≤ f (λ a ). Since α(λ a ) + α(λ b ) and α(λ a ) + α(λ b ) are integers and λ a ≤ λ a , we deduce from Equation [START_REF] Jaillet | Shortest path problems with node failures[END_REF]

α(λ a ) + α(λ b ) ≤ α(λ a ) + α(λ b ). As α(λ i ) = α(λ i ), i = 1, . . . , k -1, i = a, b, we conclude E s(λ ) ≤ E s(λ). Lemma 4. E H s (λ) ≥ E H s (λ B ) Proof. Note first that ∀λ ∈ Λ(H), E H s (λ) = E H s (λ ≤ )
, and assume λ is a non decreasing solution. We look at the pair of intervals (λ 1 , λ κ ) with the largest length difference. If |λ 1 -λ κ | ≤ 1, then λ is a balanced solution and the lemma is verified. Otherwise, we create a new solution λ by replacing the extreme intervals by a new pair of intervals of size λ

1 = n-κ-1 i=2 λi 2 and λ κ = n-κ-1 i=2 λi 2 . As λ 1 + λ κ = λ 1 + λ κ , by Lemma 3, we deduce E H s (λ) ≥ E H s (λ ). We denote λ = λ ≤ the non decreasing solution induced by λ . Then, E H s (λ ) = E H s (λ ). Consequently, note that ∀j = 1, . . . , κ, λ 1 ≤ λ j ≤ λ κ We can make two observations: first λ 1 ≥ λ 1 and λ κ ≤ λ κ , thus λ κ -λ 1 ≤ λ κ -λ 1 .
It means that the maximum length difference between intervals in the newly created solution doesn't increase compared to the original solution. The second observation is that λ 1 > λ 1 and λ κ < λ κ . This ensures that after at least n 2 iterations, the maximum length difference strictly decreases. Therefore we can iterate this process with the new extreme intervals (λ 1 and λ κ ) until we get a solution whose extreme intervals lengths differ by at most 1, in which case all intervals differ by at most 1. This is then a balanced solution, hereby the proof is completed. Proposition 3. λ B ∈ arg min{E H s (λ), λ ∈ Λ(H)}. Proof. Using Lemmas 1 and 4, Equation ( 6) and ∀λ ∈ Λ(H), we get:

E H s (λ) ≥ E H s (λ) ≥ E H s (λ B ) = E H s (λ B ).
We then conclude: 4)). As λ B corresponds to a unique solution K B in the case of paths, the proof is complete.

Theorem 1. K B ∈ arg min{E Pn+1 (K), K ∈ K(P n+1 )} Proof. As λ B ∈ arg min{E Pn+1 s (λ), λ ∈ Λ(P n+1 )} (Proposition 2 ), and λ B ∈ arg min{E Pn+1 s (λ), λ ∈ Λ(P n+1 )} (Proposition 3 ), then λ B ∈ arg min{E Pn+1 (λ), λ ∈ Λ(P n+1 )} (see Equation (

The case of cycles

Proposition 4. K B ∈ arg min{E Cn (K), K ∈ K(C n )}
Proof. (Sketch) Given an instance C n of our problem with k centers, we match an instance P n+1 of Probabilistic k-Center with k + 1 centers with the extremity nodes (1, n + 1) part of any feasible solution K P of P n+1 . Thus, to any solution K P ∈ K(P n+1 ) we can match a solution K C ∈ K(C n ) of size k. Since it is the lengths of the segments induced by K C that distinguish a solution from another on C n , K C matches K P if they both induce a series of k segments of same lengths. We assume then, without loss of generality for C n , that λ 1 is the length of the shortest segment. The values of the solutions K C and K P verify the following relations: E Cn (K C ) = n+1 n E Pn+1 (K P ) -min{r K P 1 , r K P n+1 } and E Cn (K C ) = n+1 n E Pn+1 (K P ) -(λ 1 -1) . By Theorem 1, we know that a balanced solution K B P minimizes E Pn+1 (K P ). In addition K B P maximizes the value of the segment of minimum length, λ B 1 . Then K B C , the solution on C n matching K B P , minimizes E Cn (K), ∀K ∈ K(C n ). As E Cn (K B C ) = E Cn (K B C ), Lemma 1 and Equation ( 6) induce E Cn (K B ) = E Cn (K B ) ≤ E Cn (K) ≤ E Cn (K) for all K ∈ K(C n ). It concludes the proof.

To our knowledge, this paper introduces the first probabilistic version of Minimum k-Center. As illustrated in this work, defining the problem already leads to interesting discussions. So far, we have considered only single node disruption scenarios under a uniform distribution of probabilities and for a modification strategy that preserves the location of the centers but affects only the allocation. Even though relatively restrictive, this version is natural for our application and is already non-obvious. Then, we propose an explicit solution on paths and cycles. The main idea is to express the objective function as the sum of two parts (contribution of the skeleton and the body) and then prove independently that the solution minimizes simultaneously both terms. This approach might be used in a more general setting. Finally we prove that this restrictive version is already NP-hard to approximate it within a factor 20 19 on planar graphs of bounded degree 3. This motivates investigating the complexity status of this version on more restrictive classes of graphs, in particular on subgrids (subgraphs of grids), that correspond to some real case applications. Minimum k-Center is polynomial on trees [START_REF] Kariv | An algorithmic approach to network location problems. I: The p-centers[END_REF]; it motivates studying the complexity of Probabilistic k-Center on trees, which, to our knowledge, remains open. The next question will be to design approximation algorithms for the hard cases and a third objective will be to consider larger ranges of impact and any probabilities. Indeed, our analysis on paths and cycles cannot be immediately extended to non uniform probability systems.

  {D j (x, K)} = max q∈{1,...,κ}:µq ∈µi { λq 2 }. Now we look at max x∈µi {D j (x, K)}. The evacuation paths on segment

Figure 3 :

 3 Figure 3: Evacuation distances to the 4-center {0, 5, 8, 18} in the scenario s 5 .

Lemma 3 .

 3 Given an initial solutionλ ∈ Λ(H), with λ a + λ b = m, λ a ≥ λ b and |λ a -λ b | ≥ 2 for some 1 ≤ b ≤ a ≤ κ, we define a solution λ such that λ a + λ b = m, |λ a -λ b | ≤ 1, λ a ≥ λ b and λ i = λ i , ∀i = 1, . . . , κ, i = a, b. Then we have E H s (λ ) ≤ E H s (λ).Proof. Let us denote α(λ a ) = j∈µa\K max{j -v a , v a+1 -j} the contribution of µ a to the value of E s(λ).

We acknowledge the support of GEO-SAFE, H2020-MSCA-RISE-2015 project #691161.

Complexity result

The case of planar graphs and in particular with low degree, is very natural for our application. It motivates us investigating the complexity status of our problem in restricted classed of planar graphs to better discriminate polynomial cases and hard cases.

Minimum Dominating Set is shown NP-hard on planar graphs of maximum degree 3 in [START_REF] Kariv | An algorithmic approach to network location problems. I: The p-centers[END_REF]. More precisely the authors refer to a private communication by David S. Johnson and give the reduction but not the complete proof. The following lemma allows to prove it and will be required later.

The reduction is from Minimum Vertex Cover in planar graphs of maximum degree 3 [?]. This does not imply immediately the hardness of our problem. Indeed, we defined the Probabilistic k-Center as the case with fixed uniform probabilities 1 |V | , while k-Center can only be seen as the specific case where the probabilities are all zeros. In this section, we will show an inapproximability result for Probabilistic k-Center on planar graphs of maximum degree 3 .

Given a planar graph G = (V, E), one builds a graph G = (V , E ) by replacing each edge uv by a C 4 a uv b uv c uv d uv , linking a uv and c uv to u and v, respectively. Proof. Consider U ⊂ V a vertex cover of G of size t. We define the set U E as follows. For every edge uv ∈ E, if v / ∈ U , we add c uv to U E . If both u and v are in U , then we add either a uv or c uv to

Assume conversely that G has a dominating set K ⊂ V of cardinality t + |E|. For every edge uv ∈ E, we necessarily have K ∩ {a uv , b uv , c uv , d uv } = ∅ to cover vertices b uv and d uv . In the meanwhile, it is never interesting to take b uv or d uv , since it would always be possible to modify a solution using b uv and/or d uv into a solution using none them and of the same size. Thus we can always transform K into a dominating set satisfying ∀uv ∈ E, |K ∩ {a uv , c uv }| = 1, K ∩ {b uv , d uv } = ∅. It remains to prove that K ∩ V is a vertex cover of G. Consider an edge uv ∈ E and the unique vertex x ∈ K ∩ {a uv , c uv }. Since K is a dominating set, if x = a uv , then v ∈ K ∩ V and if x = c uv , then u ∈ K ∩ V . This completes the proof.

Consider a planar graph G and assume it does not have pending vertices (vertices of degree 1), then using the previous construction, G has no pending vertex. Assume G has a minimal vertex cover of size t, we define k t = t + |E| and consider a dominating set K of size k t in G , with exactly one vertex in {a uv , c uv } and none in {b uv , d uv } for any edge uv ∈ E. Seeing K as a k t -center, we now evaluate the related probabilistic radius for any scenario in the graph G . Lemma 6. Using the above notations we have:

Proof. Since G is triangle-free with no pending vertex, and K is a dominating set, then we have:

. By definition of K , {v 1 , . . . , v d } ⊂ K and thus {a uv1 , . . . , a uv d } ⊂ K , so whatever the escaping direction, people located on u will reach a center at distance 1. Since K is a dominating set in G , it remains a dominating set in G \ {u}, which proves r K u = 1. Suppose now u ∈ V ∩ K . Since the considered vertex cover is minimal, there is j ∈ {1, . . . , d} such that v j / ∈ K and thus K ∩ {a uvj , b uvj , c uvj , d uvj } = {c uvj }. Then, the evacuation distances of a uvj is 2, and thus

∈ K and only one neighbor of u is in K , inducing an evacuation distance of 2 for u.

Suppose finally u ∈ {a vw , c vw } for vw ∈ E. If u / ∈ K exactly one of its three neighbors is in K and its evacuation distance is also 2. If finally u ∈ K , the evacuation distance of b vw and d vw becomes 2. So, in all cases but the first one r K u = 2 and the proof is complete.

Our proof will require another transformation and the property mentioned in the next lemma. Consider a planar graph, G = (V, E) of degree at most 3. For a given q ∈ N, q ≥ 2, we transform G into G q = ( V q , E q ) as follows. We choose randomly an orientation of edges in E and we replace every edge uv ∈ E oriented from u to v by the path P q uv = {u, x 1 uv , x 2 uv , . . . , x 2q uv , v}. Note that | V q | = |V | + 2q|E| and E q = (2q + 1)|E|.

Lemma 7. For any t ≤ |V |, G = (V, E) has a minimum vertex cover of size t if and only if G q = ( V q , E q ) has a minimum vertex cover of size t + q|E|.

Proof. Assume first U ⊂ V is a minimum vertex cover of size t in G: ∀uv ∈ E, {u, v} ∩ U = ∅. Then we build U q ⊂ V q in G q as follows. We initialize U q with all vertices of U . Then, for every edge uv ∈ E, if u ∈ U , we add vertices

In both cases we have added exactly q vertices and all edges of P q uv are covered. Thus, | U q | = t + q|E|. U q is minimum because we need the t vertices of the set U to cover at least |E| edges ux 1 uv , and we need at least q|E| different vertices to cover {x 1 uv , x 2 uv , . . . , x 2q uv : ∀uv ∈ E}. Assume now that G q has a minimum vertex cover U q of size t + q|E|. For every uv ∈ E, P q uv is covered by at least q + 1 vertices. If u, v ∈ U q , we can transform U q into U q such that u or v is in U q . Then |( V q \ V ) ∩ U q | = q|E| and thus |V ∩ U q | = t. It remains to prove that U = V ∩ U q is a minimum vertex cover. U is a vertex cover because if u ∈ U q , then P q uv is covered in G q , thus uv is covered in G. If U is not minimum, then suppose U * is a minimum vertex cover of size t * < t. Then by the transformation given in paragraph 1 we can get a vertex cover for G q of size t * + q|E| < | U q | which contradicts our initial hypothesis. Thus U is minimum.

The last Lemma we will need for our hardness proof is certainly a known remark but we show it since we did not find any reference for it. Lemma 8. Minimum Vertex Cover is NP-hard in planar graphs with vertices of degree 2 or 3.

Proof. The decision version of Minimum Vertex

Cover is known to be NP-complete on planar graphs of maximum degree 3 [START_REF] Kariv | An algorithmic approach to network location problems. I: The p-centers[END_REF]. Consider a planar graph G of maximum degree 3 and with a pending vertex v. Consider the graph G obtained from G by adding a triangle and linking one of its vertices with v (v is then of degree 2 in G ). G is planar with maximum degree 3 and one pending vertex less than G. Moreover, G has a vertex cover of size t if and only if G has a minimum vertex cover of size t + 2, which concludes the proof.

We now are ready to prove the main result of this section. Recall that we consider in this paper Probabilistic k-Center under a uniform probability distribution. Note that if k was a fixed constant, the number of k-centers would be polynomial and the problem itself could be polynomially solved on any graph. So, we assume that k is part of the instance. Theorem 2. There is no polynomial time approximation for Probabilistic k-Center guaranteeing a ratio less than 20 19 for planar graphs of degrees 2 or 3, unless P=NP.

Proof. The proof is by contradiction. Let ρ satisfy 1 < ρ < 20 19 . Consider ε > 0 such that ρ < 20+2ε 19+2ε < 20 19 . Take q ∈ N, such that 5 q ≤ ε and q ≥ 2. We suppose we have a polynomial approximation algorithm A for Probabilistic k-Center, admitting as argument a planar graph H of degrees 2 or 3 and the number k of centers, and guaranteeing the approximation ratio ρ. We then will show how to use this algorithm to solve the Minimum Vertex Cover problem on planar graphs with vertex degrees 2 or 3. Lemma 8 will give the contradiction, unless P=NP.

Consider a planar graph G = (V, E) with vertex degrees in {2, 3}, instance of Minimum Vertex Cover. Consider the graph G q = ( V q , E q ) and then G q = ( V q , E q ). We have in particular:

Denoting by τ (H) and η(H)| the minimum size of a vertex cover and a dominating set in a graph H, respectively, we deduce from Lemmas 5 and 7:

We apply the hypothetical approximation algorithm A on G q for different values of k, starting with k = 1 and augmenting it.

Suppose first we use k < η( G q ) centers and the algorithm computes a center K . Then, the non-probabilistic radius is at least 2 since K cannot be a dominating set in G q and consequently:

Suppose now we use k = η( G q ) = τ ( G q ) + | E q | centers. Using Lemma 5 on graph G q , there is a k-center K of graph G q satisfying the conditions of Lemma 6 and then, this Lemma ensures:

We deduce, using Relations 11 and 12:

where the last inequality holds because τ (G) < |V |. So, we have:

Since G has vertices of degree at least 2, we have V ≤ |E|, thus:

where the last inequality holds since 5 q ≤ ε. As a consequence, since an optimal probabilistic solution K * will satisfy E( K * ) ≤ E( K ), the approximation algorithm A will determine an approximated center K in G q of value:

Note that, given a center K , computing its probabilistic radius can be done in polynomial time since, for any vertex v ∈ V q , computing r K v can be performed using any minimum path algorithm. So, we apply successively the approximation algorithm A on the graph G q for increasing values of k, starting with k = 1, until the computed center K satisfies E( K ) < 2. Equations 12, 13 and14 ensure that, the algorithm stops after k = η( G q ) = τ ( G q ) + | E q | iterations and then, τ (G) = | K | -(3q + 1)|E|. Since constructing G q and evaluating E( K ) can be done in polynomial time, and since algorithm A will be run less than |V | times, the whole process is polynomial. This is a contradiction if P =NP, and the proof is complete. Proof. In H, at least one vertex out of two consecutive vertices is in K B . Therefore λ B i ≤ 2, ∀i ∈ 1, . . . , κ, and by Equations ( 7) and ( 8) we can state that r K

Suppose K a non balanced but optimum solution on H. As K is non balanced, ∃i ∈ 1, . . . , κ : λ i ≥ 3. Then for j ∈ µ i , r K j ≥ 2 (see Equations ( 7) and ( 8)). And for j ∈ H \ {µ i }, r K j ≥ λi 2 ≥ 1. Then j∈V r K j > n and E H (K) > pn, which is contradictory with the hypothesis. Thus a non balanced solution can't be optimum on H for k ≥ n 2 and the lemma is proven.

Proof of Lemma 1

Lemma

) and E H (λ B ) = E H (λ B ).

Proof. In H we have: λ B q ∈ { n κ , n κ }, q ∈ {1, . . . , κ}. As k < n 2 , then max q∈{1,...,κ}

q -1, ∀q = 1, . . . , κ. The same holds for a balanced solution λ B in with λ B q ∈ { n k , n k }. Then given Equation ( 7), we obtain r K B j = r K B j : ∀j ∈ K, thus E H s (λ B ) = E H s (λ B ). We also observe that ∀i = 1, . . . , κ, ∀j ∈ µ B i \K, δ j (j, K B ) ≥ max{j -v i , v i+1 -j} ≥ Then given Equation( 8), we obtain r