Nicolas Boria
email: boria@lamsade.dauphine.fr

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

Vangelis Th Paschos
email: paschos@lamsade.dauphine.fr

On the probabilistic min spanning tree problem *

We study a probabilistic optimization model for min spanning tree, where any vertex v i of the input-graph G(V, E) has some presence probability p i in the final instance G ′ ⊂ G that will effectively be optimized. Suppose that when this "real" instance G ′ becomes known, a spanning tree T , called anticipatory or a priori spanning tree, has already been computed in G and one can run a quick algorithm (quicker than one that recomputes from scratch), called modification strategy, that modifies the anticipatory tree T in order to fit G ′ . The goal is to compute an anticipatory spanning tree of G such that, its modification for any G ′ ⊆ G is optimal for G ′ . This is what we call probabilistic min spanning tree problem. In this paper we study complexity and approximation of probabilistic min spanning tree in complete graphs under two distinct modification strategies leading to different complexity results for the problem. For the first of the strategies developed, we also study two natural subproblems of probabilistic min spanning tree, namely, the probabilistic metric min spanning tree and the probabilistic min spanning tree 1,2 that deal with metric complete graphs and complete graphs with edge-weights either 1, or 2, respectively.

Introduction

The basic problematic of probabilistic combinatorial optimization (in graphs) is the following. We are given a graph G(V, E) on which we have to solve some optimization problem Π. But, for some reasons depending on the reality modeled by G, Π is only going to be solved for some subgraph G ′ of G (determined by the vertices that will finally be present) rather than for the whole of G. The measure of how likely it is that a vertex v i ∈ V will belong to G ′ (i.e., will be present for the final optimization) is expressed by a probability p i associated with v i . How we can proceed in order to solve Π under this kind of uncertainty?

A first very natural idea that comes to mind is that one waits until G ′ is specified (i.e., it is present and ready for optimization) and, at this time, one solves Π in G ′ . This is what is called reoptimization. But what if there remains very little time for such a computation? In this case, another way to proceed is the following. One solves Π in the whole of G in order to get a feasible solution (denoted by S), called a priori or anticipatory solution, which will serve her/him as a kind of benchmark for the solution on the effectively present subgraph G ′ . One has also to be provided with an algorithm that modifies S in order to fit G ′ . This algorithm is called modification strategy (let us denote it by M) and produces from S a solution S ′ that is feasible for Π in G ′ . The objective now becomes to compute an anticipatory solution that, when modified by M, remains "good" for any subgraph of G (if this subgraph is the one where Π will be finally solved). This amounts to computing a solution that optimizes a kind of expectation of the value of the modification of S over all the possible subgraphs of G, i.e., the sum of the products of the probability that G ′ is the finally present graph multiplied by the value of S ′ . Obviously, the presence-probability of G ′ is the probability that all of its vertices are present and the other vertices outside G ′ are absent. This expectation, depending on both the instance of the deterministic problem Π, the vertex-probabilities, and the modification strategy adopted, is called the functional and is expressed by:

E(G, S, M) = V ′ ⊆V Pr V ′ m G ′ , S ′ , M (1)
where

Pr[V ′ ] = v i ∈V ′ p i v i ∈V \V ′ (1-p i )
is the distribution describing probability of occurrence of a specific subset V ′ ⊆ V , i.e., of the graph G[V ′ ] and m(G ′ , S ′ , M) is the value of the solution S ′ produced by application of M on the anticipatory solution S.

Seen in this way, the probabilistic version probabilistic Π of a (deterministic) combinatorial optimization problem Π becomes another equally deterministic problem Π ′ , the solutions of which have the same feasibility constraints as those of Π but with a different objective function where vertex-probabilities intervene. In this sense, probabilistic combinatorial optimization is very close to what in the last couple of years has been called "one stage optimisation under independent decision models", an area very popular in the stochastic optimization community. It is hopefully clear from [START_REF] Averbakh | Probabilistic a priori routing-location problems[END_REF] and from the whole discussion above, that m(G ′ , S ′ , M) strongly depends on the modification strategy M used to adapt the anticipatory solution S to the present graph G ′ . So, both E(G, S, M) and the a priori solution S * optimizing it, also strongly depend on M. In other words, as we will see later, for a fixed instance I of a deterministic problem Π, two distinct modification strategies induce two distinct probabilistic problems having I and Π as common deterministic supports. These two distinct problems may have very different functionals and, consequently, different optimal anticipatory solutions that induce very different complexities for computing them.

What are the main mathematical problems dealing with probabilistic consideration of a problem Π in the sense discussed above? One can identify at least five interesting mathematical and computational problems dealing with probabilistic combinatorial optimization:

1. write the functional down in an analytical closed form;

2. if such an expression of the functional is possible, prove that its value is polynomially computable (this amounts to proving that the decision version of the modified problem Π ′ belongs to NP);

3. determine the complexity of the computation of the optimal a priori solution, i.e., of the solution optimizing the functional (in other words, determine the computational complexity of Π ′ ); 4. if Π ′ is NP-hard, study polynomial approximation issues;

5. always, under the hypothesis of the NP-hardness of Π ′ , determine its complexity in the special cases where Π is polynomial, and in the case of NP-hardness, study approximation issues.

Let us note that, although curious, point 2 in the above list is neither trivial nor senseless. Simply consider that the summation for the functional includes, in a graph of order n, 2 n terms (one for each subgraph of G). So, polynomiality of the computation of the functional is, in general, not immediate. Several optimization frameworks have been introduced by the operations research community for handling data uncertainty, the most well developed being Stochastic programming (see [START_REF] Birge | Introduction to stochastic programming[END_REF][START_REF] Dantzig | Linear programming under uncertainty[END_REF][START_REF] Prekopa | Stochastic programming[END_REF] for basics) and Robust discrete optimization (see, for example, [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF]). The framework of Probabilistic Combinatorial Optimization where our work is located was introduced by [START_REF] Jaillet | Probabilistic traveling salesman problem[END_REF][START_REF] Bertsimas | Probabilistic combinatorial optimization problems[END_REF]. In [START_REF] Averbakh | Probabilistic a priori routing-location problems[END_REF][START_REF] Bertsimas | Probabilistic combinatorial optimization problems[END_REF][START_REF] Bertsimas | On probabilistic traveling salesman facility location problems[END_REF][START_REF] Bertsimas | The probabilistic minimum spanning tree problem[END_REF][START_REF] Bertsimas | A priori optimization[END_REF][START_REF] Jaillet | Probabilistic traveling salesman problem[END_REF][START_REF] Jaillet | A priori solution of a traveling salesman problem in which a random subset of the customers are visited[END_REF][START_REF] Jaillet | Shortest path problems with node failures[END_REF][START_REF] Jaillet | The probabilistic vehicle routing problem[END_REF], restricted versions of routing and network-design probabilistic minimization problems (in complete graphs) have been studied under the robustness model dealt here (called a priori optimization). In [START_REF] Bianchi | Local search for the probabilistic traveling salesman problem: correlation to the 2-p-opt and 1-shift algorithms[END_REF], the analysis of the probabilistic minimum travelling salesman problem, originally performed in [START_REF] Bertsimas | Probabilistic combinatorial optimization problems[END_REF][START_REF] Jaillet | Probabilistic traveling salesman problem[END_REF], has been revisited and refined. Several other combinatorial problems have been recently treated in the probabilistic combinatorial optimization framework, including minimum coloring ( [START_REF] Murat | On the probabilistic minimum coloring and minimum kcoloring[END_REF][START_REF] Bourgeois | Probabilistic coloring of bipartite and split graphs[END_REF]), maximum independent set and minimum vertex cover ( [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] Th | Steiner forests on stochastic metric graphs[END_REF][START_REF] Th | Probabilistic models for the steiner tree problem[END_REF]). Note also that probabilistic minimum spanning tree has also studied by [START_REF] Bertsimas | The probabilistic minimum spanning tree problem[END_REF] but under a very different probabilistic model.

Preliminaries

We apply in this paper the probabilistic combinatorial optimization setting just described in the minimum spanning tree problem. Given an edge-weighted graph G(V, E), with positive edge weights d : E → Q + , the minimum spanning tree problem (min spanning tree) consists of determining a minimum total edge-weight tree spanning V . min spanning tree is a celebrated problem, very frequently modeling several kinds of networks in transports, communications, energy, logistics, etc.

The most popular algorithm for min spanning tree is the seminal Kruskal's Algorithm ( [START_REF]On the shortest spanning subtree of a graph and the traveling salesman problem[END_REF]) which consists of sorting edges in non-decreasing order with respect to their weights, and of inserting them in the current solution provided that they do not create cycles with those already inserted. The complexity of this algorithm is O(m log n) where m = |E| and n = |V |. Several improvements have been performed upon this result, for instance, the O(m log log n) result given independently by [START_REF] Yao | (|E| log log |V |) algorithm for finding minimum spanning trees[END_REF] and [START_REF] Cheriton | Finding minimum spanning trees[END_REF]. More recently, [START_REF] Chazelle | A minimum spanning tree algorithm with inverse-ackerman type complexity[END_REF] proposes an algorithm for min spanning tree (the best known until now, to our knowledge) with running time O(mα(m, n)), where α is the functional inverse of Ackerman's function defined by [START_REF] Tarjan | Efficience of a good but not linear set-union algorithm[END_REF]. We also quote an implementation of Prim's algorithm (this is another famous min spanning tree-algorithm) using Fibonacci heaps that works in O(max{m, n log n}) ( [START_REF] Cormen | Introduction to Algorithms[END_REF]).

min spanning tree has been actively studied under several optimization models like online computation, dynamic optimization, etc. Its study always motivates numerous researchers in theoretical computer science and in operational research.

The formal definition of probabilistic min spanning tree under modification strategy M is as follows. Consider a complete weighted graph G(V, E) on n vertices, with edge weights given by a function d

: E → Q + . Set V = {v 1 , v 2 , . . . , v n }. Each vertex v i ∈ V ,
is associated with a presence probability p i ∈ Q + measuring, as already mentioned, how likely is that v i will be present in the instance where probabilistic min spanning tree will really be solved. We assume that subgraph G ′ (V ′ , E ′ ) of G materializes as the outcome of n independent Bernoulli trials, one per

vertex v i ∈ V : v i ∈ V ′ with probability p i . Then, E ′ = {(u, v) ∈ E : u ∈ V ′ and v ∈ V ′ }.
Let us note that it seems to be natural that, for a fixed modification strategy M and for some anticipatory spanning tree T , some basic properties of its structure must be preserved in any tree T ′ built when M adjusts T to G ′ (V ′ , E ′ ), for any V ′ ⊆ V . Such a basic property is, for instance, the relation "predecessor-successor" in T . In order that this relation is preserved in any T ′ , we assume that there exists a vertex, denoted by v 1 with p 1 = 1. The assumption that the input-graph is complete is made in order to ensure connectivity of the tree T ′ for any subgraph G ′ ⊆ G; in any case if the real-world problem at hand implies non-complete graphs, one can complete them by "appropriately heavy" edges.

Consider an application of probabilistic min spanning tree coming from message broadcasting in a computer network ([9]). We use there a tree spanning the vertices of this network. Assuming that the weight of an edge of the network represents the transmission-cost on the link represented by this edge, we look for a minimum-cost tree spanning all the vertices of the underlying network. In distributed computation, the structure of a tree allows broadcasting from the root to the leaves, and vice-versa, as well as resolution of several problems dealing with synchronization, or mutual exclusion ( [START_REF] Butelle | Contribution à l'algorithmique distribuée de contrôle : arbres couvrants avec et sans contraintes[END_REF]). Assume that each vertex v i of the network can fail or be unavailable with some probability p i , except some vertex, denoted by v 1 , that represents the central server that "never" fails (or very rarely). In such case, we can consider that the presence probability of v 1 is 1 and of any other vertex v i is 1 -p i . Given some modification strategy, motivated by the particular application to be handled, the objective is to determine some spanning tree with minimum expectation. Other applications dealing with probabilistic min spanning tree can be found in [START_REF] Bertsimas | Probabilistic combinatorial optimization problems[END_REF].

In what follows, we design two modification strategies for probabilistic min spanning tree and study the two distinct probabilistic optimization problems derived. In Section 4 we design strategy CLOSEST_ANCESTOR, and derive an analytic expression of the functional of the solutions T * . We next show that, under this strategy the problem of the a priori optimization, i.e., the problem of determining an anticipatory solution minimizing the functional, is NP-hard in general complete graphs (Section 4.1). Subsequently, we study complexity of the probabilistic min spanning tree problem when dealing with particular cases of vertex-probabilities values and/or edge weights (Section 4.2.1) and particular cases of anticipatory solutions (Section 4.2.2). We next derive polynomial-time approximation results for metric graphs (Section 4.3.1) and for graphs where edge-weights are either 1 or 2 (Section 4.3.2). Next, in Section 5, we devise another modification strategy for probabilistic min spanning tree, called ROOT, and show that, under this strategy, probabilistic min spanning tree is polynomial.

Let us note that a complementary framework to the one of the a priori optimization, is the reoptimization consisting of solving ex nihilo and optimally the portion of the instance presented for optimization. Reoptimization is introduced in [START_REF] Jaillet | Probabilistic traveling salesman problem[END_REF]. Let opt(G ′ ) refer to the weight of the optimum spanning tree on G ′ for every subgraph G ′ (V ′ , E ′ ) of G. The expected minimum weight over the distribution of subgraphs of G, i.e., the functional of reoptimization is:

E * (G) = V ′ ⊆V Pr V ′ opt G ′ (2)
Obviously, denoting by T * M the optimal anticipatory solution of probabilistic min spanning tree, under any modification strategy M, it holds that:

E * (G) E (G, T * M , M) (3)
In Section 3, we perform further study of reoptimization and exhibit some relations between it and (deterministic) min spanning tree. For simplicity, in Sections 4 and 5 we simplify notations and omit strategies' names from the expressions for the functionals. However, we underline once more the fact that the probabilistic versions of probabilistic min spanning tree studied in these sections are indeed two distinct optimization problems.

Reoptimization and min spanning tree

We study in this section relations between the value of the expectation E * (G) in the reoptimization setting and the optimal value of the (deterministic) min spanning tree. Our goal is to prove the following result.

Proposition 1. Consider a complete edge-weighted graph G defined on a set V of n vertices V = {v 1 , . . . , v n } associated with a system of vertex probabilities p 1 = 1, p i = p, i = 2, . . . , n. Denote by opt(G) the value of an optimal solution T * for (deterministic) min spanning tree.

Then, E * (G) p opt(G).

Proof. Since vertex v 1 (assumed to be the root of every tree solution of min spanning tree in every subgraph of G) is always present, setting

G ′ = G[V ′ ],
(2) can be written as:

E * (G) = n k=2 p k-1 (1 -p) n-k × V ′ ⊆V |V ′ |=k opt G ′ (4) Set D k = V ′ ⊆V ,|V ′ |=k opt(G ′ ).
Then, (4) becomes:

E * (G) = n k=2 p k-1 (1 -p) n-k D k (5)
We first show that:

D k n -2 k -2 opt(G) (6)
Denote by E[T * ] the edge-set of the tree T * . Then, for every i = 1, set

V i = V \ {v i } and denote by f (i), the father of i in T * . Setting G i = G[V i ],
we have for every

(v i , v f (i) ) ∈ E[T * ], i = 1: opt (G i ) + d i,f (i) opt(G) (7)
since a minimum spanning tree of G i plus some edge connecting v i to it is a tree of G. Summing (7) over i = 2, . . . , n, we get:

n i=2 opt (G i ) + n i=2 d i,f (i) (n -1) opt(G) (8)
Moreover, obviously, it holds that

n i=2 d i,f (i) = opt(G) (9)
From ( 8) and ( 9) the following is deduced:

D n-1 = n i=2 opt (G i ) (n -2) opt(G) (10)
Let us now consider the t = C k-1 n-1 subsets of V of size k (recall that v 1 is omnipresent), A 1 , A 2 , . . . , A t . For any i, set A i,j = A i \ {j}. With a reasoning completely similar to the above, setting G i,j = G[A i,j ], we can derive:

j∈A i opt (G i,j ) (k -2) opt (G i ) (11)
t i=1 j∈A i opt (G i,j ) (k -2) t i=1 opt (G i ) = (k -2)D k (12)
where ( 12) is obtained summing [START_REF] Cheriton | Finding minimum spanning trees[END_REF] for every i. Since in the lefthand side term each of the C k-2 n-1 subsets of V (of cardinality k -1) is taken into account n -k + 1 times, this term can be written:

t i=1 j∈A i opt (G i,j ) = (n -k + 1)D k-1 (13)
Indeed, w.l.o.g. let us assume that

A 1 = {v 1 , v 2 , . . . , v k-1 , v k }, A 2 = {v 1 , v 2 , . . . , v k-1 , v k+1 }, A 3 = {v 1 , v 2 , . . . , v k-1 , v k+2 }, . . . , A n-k+1 = {v 1 , v 2 , . . . , v k-1 , v n }. Let us consider set A 1,k obtained from A 1 by removing vertex v k : A 1,k v 1 , v 2 , . . . , v k-1 , v k A 1 , . . . , v n
We build in the same way pairs

(A 2 , A 2,k+1 ), (A 3 , A 3,k+2 ), . . . , (A n-k+1 , A n-k+1,n ): A 2,k+1 v 1 , v 2 , . . . , v k-1 , v k+1 A 2 , v k , v k+2 , . . . , v n . . . A n-k+1,n v 1 , v 2 , . . . , v k-1 , v n A n-k+1 , v k , . . . , v n-1
We can easily see that [START_REF] Cormen | Introduction to Algorithms[END_REF].

A 1,k = A 2,k+1 = A 3,k+2 = . . . = A n-k+1,n ; hence, any of the C k-2 n-1 distinct subsets of V of cardinality k -1 can be obtained using n -k + 1 different ways, that proves
Combining ( 12) and ( 13) we get:

D k-1 k -2 n -k + 1 D k (14)
By successively applying [START_REF] Dantzig | Linear programming under uncertainty[END_REF] and using [START_REF] Chazelle | A minimum spanning tree algorithm with inverse-ackerman type complexity[END_REF] we derive:

D k k -1 n -k D k+1 (k -1)k (n -k)(n -(k + 1)) D k+2 . . . (k -1)k . . . (n -3) (n -k)(n -(k + 1)) . . . (n -(n -2)) D n-1 (k -1)k . . . (n -3)(n -2) (n -k)(n -(k + 1)) . . . (n -(n -1)) opt(G) = (n -2)! (k -2)!(n -k)! opt(G) = n -2 k -2 opt(G)
as claimed in [START_REF] Bianchi | Local search for the probabilistic traveling salesman problem: correlation to the 2-p-opt and 1-shift algorithms[END_REF]. Combining it with (5), we get:

E * (G) n k=2 p k-1 (1 -p) n-k n -2 k -2 opt(G) = p opt(G)
completing so the proof of the proposition. Combining (3) and Proposition 1, the following holds, for any modification strategy M:

E (G, T * M ) p opt(G) (15)
Note that equality in ( 15) is attained for p = 1.

probabilistic min spanning tree under CLOSEST_ANCESTOR

Consider a tree T spanning V and number vertices in T in a left-to-right breadth-first-search (bfs) way. Consider a subgraph

G ′ (V ′ , E ′ ) = G[V ′ ] of G induced by a set V ′ ⊆ V .
The modification strategy (adjusting T to a spanning tree T ′ of G ′ and denoted by CLOSEST_ANCESTOR in what follows) that will be analyzed in this section works as follows:

• remove the vertices of V \ V ′ and the edges of E incident to these vertices; let F (V ′ ) = {T 1 , T 2 , . . . , T k } be the so-obtained forest and assume that v 1 ∈ V (T 1 ) and that, for i, j = 2 . . . , k, i < j if the index of the root of T i is smaller than that of the root of T j ;

• for i = 2, . . . , k add as father of the root of T i its largest-index ancestor that is still present in V (T ).

Note that, given two vertices v j and v l with j < l (in the bfs numbering of T ), if v j is not an ancestor of v l in T , then edge (v j , v l ) will never belong to any T ′ modification of T for any

V ′ ⊆ V . Clearly, the complexity of CLOSEST_ANCESTOR is O(n).
Note also that, with respect to the application sketched in Section 1, this strategy allows to maintain the same order of broadcasting to the several internal nodes of the anticipatory tree, independently on the subinstance that will finally be realized. Our goal in this section is to study the following problem: find an algorithm for taking "good" a priori decisions, i.e., that determines a spanning tree T * , that optimizes E(G, T ) under modification strategy CLOSEST_ANCESTOR ; this is probabilistic min spanning tree (under strategy CLOSEST_ANCESTOR). In what follows, we show that this problem is NP-hard in general complete graphs with p 1 = 1. We then study approximation of this problem in metric graphs as well as in a particular subclass of them where edge-weights are either 1 or 2. The approximation ratio is defined as E(G, T )/E(G, T * ).

The complexity of probabilistic min spanning tree

The following result holds for the functional E(G, T ) associated with an anticipatory spanning tree T and the modification strategy CLOSEST_ANCESTOR.

Proposition 2 . Consider a complete graph G(V, E), provided with a vertex-probability system (p i ) i=1,...,n with p 1 = 1, any edge (v i , v j ) of which has weight d ij and a spanning tree T of G. Then, the expectation associated with CLOSEST_ANCESTOR can be expressed by:

E(G, T ) = (v i ,v j )∈T p i p j d ij + v i ∈V v j ∈D(v i ) ( v i ,v j ) / ∈T p i p j v k ∈µ[v i ,v j ] (1 -p k ) d ij ( 16
)
where D(v i ) is the set of successors of v i in T and µ[v i , v j ] is the set of vertices in the (unique) path of T from v i to v j not including neither of them.

Proof. Following CLOSEST_ANCESTOR, if (v i , v j ) ∈ T , then this edge will be in

T ′ iff v i , v j ∈ V ′ ; on the other hand, if (v i , v j ) / ∈ T , then edge (v i , v j ) will be added in T ′ iff v i , v j ∈ V ′ and v j ∈ D(v i ) and every vertex in µ[v i , v j ] is not in V ′ .
From these observations we derive using (1):

E(G, T ) = V ′ ⊆V Pr V ′ m G ′ , T ′ = V ′ ⊆V Pr V ′ (v i ,v j )∈T ′ d ij = V ′ ⊆V Pr V ′ (v i ,v j )∈T ′ ∩T d ij + V ′ ⊆V Pr V ′ (v i ,v j )∈T ′ ∩(E\T ) d ij = (v i ,v j )∈T V ′ ⊆V Pr V ′ 1 {(v i ,v j )∈T ′ } d ij + (v i ,v j )∈(E\T ) V ′ ⊆V Pr V ′ 1 {(v i ,v j )∈T ′ } d ij = (v i ,v j )∈T p i p j d ij + v i ∈V v j ∈D(v i ) ( v i ,v j ) / ∈T p i p j v k ∈µ[v i ,v j ] (1 -p k ) d ij as claimed.
Clearly, ( 16) can be computed in polynomial time. So, the following corollary holds.

Corollary 1. probabilistic min spanning tree ∈ NPO.

As already mentioned, probabilistic min spanning tree consists of determining an anticipatory spanning tree T * of G minimizing E(G, T ). Unfortunately, Proposition 2 does not derive a compact combinatorial characterization for the optimal anticipatory solution of probabilistic min spanning tree. In particular, the form of the functional does not imply solution, for instance, of some well-defined weighted version of the (deterministic) min spanning tree. This is due to the second term of the expression for E(G, T ) in [START_REF] Georgiadis | Arborescence optimization problems solvable by edmonds' algorithm[END_REF]. There, the "costs" assigned to the edges depend on the structure of the anticipatory solution chosen and of the present subgraph of G.

The decision version of probabilistic min spanning tree under CLOSEST_ANCESTOR, denoted by probabilistic min spanning tree(K) can be stated as follows: "given an edgeweighted complete graph G(V, E), provided with a vertex-probability system (p i ) i=1,...,n with p 1 = 1 and a constant K, does there exist a tree T such that E(G, T ) K?", where E(G, T ) is given by [START_REF] Georgiadis | Arborescence optimization problems solvable by edmonds' algorithm[END_REF].

Proposition 3. probabilistic min spanning tree(K) is NP-complete.
Proof. It is easy to see that probabilistic min spanning tree ∈ NP (Corollary 1). In order to show completeness, we reduce 3 exact cover to probabilistic min spanning tree. 3 exact cover is defined as follows: given a ground set X of size 3q and a collection E of 3q subsets of X each of size 3, does there exist a sub-collection E ′ = {S 1 , . . . , S q } of E such that q i=1 S i = X?" (obviously, E ′ is a partition of X).

Consider an arbitrary instance I(X, E) of 3 exact cover; we construct the following instance for probabilistic min spanning tree:

• the vertex-set V is a set of 6q + 2 vertices built by associating a vertex x i with an element

x i ∈ X, a vertex y j with a set S j ∈ E and by adding a vertex r (playing the role of the omnipresent root) and a vertex s (representing the solution); for some positive fixed constant p < 1/2, vertices x i are provided with probability p, vertices y j with probability 1 -p and vertices r and s with probability 1;

• edge-weights are defined as follows:

for every

S j = {x i 1 , x i 2 , x i 3 }, j = 1, . . . , 3q, d i 1 j = d i 2 j = d i 3 j = 1;
edges linking s to vertices y j have weight M > 3p 2 /2(1 -p) and those linking s to vertices of x i have weight M/p + 2;

edges linking r to vertices y j as well as edge (r, s) have all weight 0, while edges linking r to vertices x i have weight M/p 2 + 1;

all the other edges have arbitrarily large weight B ≫ M/p 2 + 1;

• K = q(M (1 + 2p) + 3p(p + 1)).
It is easy to see that this reduction is polynomial. It is illustrated in Figure 2 where, for readability, some edges, in particular those of weight B are omitted. We now prove that if 3 exact cover admits a solution E * , then G has a minimum spanning tree T * the shape of which is as in Figure 3 and whose value is:

x 1 x 2 x 3 x i1 x i2 x i3 x l1 x l2 x l3 x 3q-2 x 3q-1 x3q y 1 y 2 y j y k y 3q s r 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 M M M M M M M M M 0 0 0 M p + 2 M p 2 + 1
E (G, T * ) = 0 + 2q × 0 + q (1 -p)M + 3p(1 -p) × 1 + 3p(1 -(1 -p)) × M p + 2 = q M -pM + 3p -3p 2 + 3pM + 6p 2 = q [M (1 + 2p) + 3p(p + 1)] = K
In other words, we are going to show that there exists a tree spanning V with expectation at most K, iff X admits a partition among the sets of E.

The ⇒ part of the proof is easy. Given a solution E * for 3 exact cover in I(X, E), a solution T * for probabilistic min spanning tree is immediately built in G as shown in Figure 3.

x 1 x 2 x 3 x i1 x i2 x i3 x l1 x l2 x l3 x 3q-2 x 3q-1 x3q y 1 y 2 y j y k y 3q S R * Figure 3: The shape of T * .
We prove the ⇐ part by inspection of all the possible trees spanning V . Let us do two easy preliminary remarks:

• any tree using an edge of weight B has expectation greater than K;

• any tree where absent edges are replaced (following strategy CLOSEST_ANCESTOR) by edges of weight B also has expectation greater than K.

As a consequence, the trees that are to be inspected are those that any reconnection will not use edges of weight B, i.e., those that span the subgraph shown in Figure 4. There exist 16 such trees illustrated in Figures 5 to 8. For reasons of economy, in all these figures, only one out of the three children of each y i is displayed. Note that tree T 1 in Figure 5 corresponds to the optimal solution, whose full shape is shown in Figure 3.

x i y j S R 0 M M p + 2 T 6 x i y j S R M 1 M p 2 + 1 T 7 x i y j S R M 0 1 T 8 x i y j S R 1 M p 2 + 1 M p + 2
E (G, T 1 ) = 1 × 1 × 0 + 1 × (1 -p) × M + 3 × (1 -p) × p × 1 + 3 × p × (1 -(1 -p)) × M p + 2 = M (1 -p) + 3p(1 -p) + 3pM + 6p 2 = M (1 + 2p) + 3p(p + 1) E (G, T 2 ) = 3p M p 2 + 1 = 3 p × M + 3p E (G, T 3 ) = 3(1 -p)p + 3p 2 M p 2 + 1 = 3M + 3p E (G, T 4 ) = 3p M p + 2 = 3M + 6p E (G, T 5 ) = (1 -p)M + 3p M p 2 + 1 = M 1 -p + 3 p + 3p E (G, T 6 ) = (1 -p)M + 3p M p + 2 = M (4 -p) + 6p E (G, T 7 ) = (1 -p)M + (1 -p)p + 3p M p 2 + 1 + p 2 M p + 2 = M 3 p + 1 + 4p + p 2 x i y j S R M p 2 + 1 M M p + 2 T 11 x i y j S R M 0 M p + 2 T 12 x i y j S R 1 0 M p + 2
E (G, T 8 ) = (1 -p)M + 3p(1 -p) + 3p 2 M p 2 + 1 = M (4 -p) + 3p E (G, T 9 ) = 3p M p 2 + 1 + p M p + 2 + p(1 -p) = M 1 + 3 p + 6p -p 2 E (G, T 10 ) = p M p + 2 + 3p(1 -p) + 3p 2 M p 2 + 1 + (1 -p) 2 M = M 5 -2p + p 2 + 5p E (G, T 11 ) = (1 -p)M + p M p + 2 + 3p M p 2 + 1 = M 2 -p + 3 p + 5p E (G, T 12 ) = (1 -p)M + 3p M p + 2 = M (4 -p) + 6p E (G, T 13 ) = p(1 -p) + 3p M p + 2 + (1 -p) 2 M = M 3 + (1 -p) 2 + 7p -p 2 E (G, T 14 ) = p(1 -p) + 3p M p 2 + 1 = M 3 p + 4p -p 2 E (G, T 15 ) = (1 -p)M + 3p M p 2 + 1 = M 3 p + 1 -p + 3p E (G, T 16 ) = 3p M p 2 + 1 + p M p + 2 = M 3 p + 1 + 5p
Trees T 2 , T 3 , T 4 , T 9 , T 10 , T 13 and T 14 correspond to the case where y j , that is, the set S j of E is not part of a 3 exact cover-solution (in other words, the element x i of the ground set X is not covered by S j ). In this case, the best one can do for the corresponding spanning tree is to take edges (r, s) and (r, y j ). The rest of the trees sketched in Figures 5 to 8 correspond to the case where S j covers x i in some 3 exact cover-solution.

In all, E(G, T 1 ) is minimum over every other E(G, T i ), i = 2, . . . , 16 it is the only that is smaller than K. Tree T 1 corresponds to q subtrees as the first one in Figure 5 but having three leaves plus 2q subtrees that are simple edges of the form (r, y j ). Obviously, given T 1 a solution for 3 exact cover is immediately computed by considering the q sets corresponding to y-vertices of T 1 that are not leaves.

Stability of the solutions

We address in this section the question of "stability of the solutions" that can be stated as follows: "under which conditions and for what kinds of instances and/or particular structures of anticipatory solutions, an optimal solution for min spanning tree remains optimal for probabilistic min spanning tree?". We study in this section some particular but natural cases carrying over assumptions either on the values of vertex-probabilities and/or edge-weights, or on the form of the anticipatory solution.

Dealing with vertex-probabilities and edge-weights

Revisit functional's expression [START_REF] Georgiadis | Arborescence optimization problems solvable by edmonds' algorithm[END_REF]. For a vertex v i , denote by f (v i ) its father in T , by p f (i) the presence probability of f (v i ) and by A(v i ) the set of its ancestors in T . Then, ( 16) can be rewritten as:

E(G, T ) = v i ∈V \{v 1 } p i p f (i) d if (v i ) + v i ∈V \{v 1 } v j ∈A(v i )\{f (v i )} p i p j v k ∈µ[v i ,v j ] (1 -p k ) d ij = v i ∈V \{v 1 } C i (17)
where:

C i = p i p f (i) d if (v i ) + v j ∈A(v i )\{f (v i )} p i p j v k ∈µ[v i ,v j ] (1 -p k ) d ij (18)
and can be seen as the contribution of vertex v i in E(G, T ).

We assume now that edge-weights in G are identical. We can show that, if

d ij = d, (v i , v j ) ∈ E, then C i = d × p i , v i ∈ V .
In order to give some intuition about it let us consider the anticipatory tree of Figure 9, assume that edge weights in the input-graph are identical and equal to d and take, say, vertex 7. The contribution of it in ( 16) is:

C 7 = d × p 7 [p 5 + p 4 (1 -p 5 ) + p 2 (1 -p 5 ) (1 -p 4 ) + (1 -p 5 ) (1 -p 4 ) (1 -p 2 )] = d × p 7 (19)
The same holds for the contribution of any other vertex in the tree.

Indeed, consider some vertex v i ∈ V and assume, for simplicity, that vertices in the path of T from v 1 to v i are numbered from 1 to i. By writing down C i and by some algebra as previously in [START_REF] Jaillet | Shortest path problems with node failures[END_REF] we derive C i = d × p i . Hence, [START_REF] Jaillet | Probabilistic traveling salesman problem[END_REF] becomes: Figure 9: About a reinterpretation of functional's expression [START_REF] Georgiadis | Arborescence optimization problems solvable by edmonds' algorithm[END_REF].

E(G, T ) = d × n i=2 p i
Proposition 4. If edge-weights are all identical, E(G, T ) = d × n i=2 p i . In this case all the anticipatory solutions have the same value.

Corollary 2. If p 1 = 1, p i = p, i = 2, . . . , n and d ij = d, (v i , v j ) ∈ E, i = j, then, for any tree T spanning V , E(G, T ) = dp(n -1).
Discussion above can be directly generalized for deriving a general upper bound for E(G, T ) and for every anticipatory solution T . Set D = max{d ij : (v i , v j ) ∈ E}. Then, (20) leads to C i D × p i and ( 17) to E(G, T ) D × n i=2 p i and the following corollary that will be used later holds. Corollary 3. If D = max{d ij : (v i , v j ) ∈ E} then, for any anticipatory solution T of probabilistic min spanning tree, E(G, T ) D × n i=2 p i .

Particular cases of anticipatory solutions: stars and paths

In what follows we deal with two particular structures of trees, the star (rooted at 1 ) and the path. We first consider the star rooted at (the omnipresent) vertex v 1 . The following result holds.

Proposition 5. Let T be a star rooted at v 1 . If T is an optimal solution for min spanning tree, then it is also an optimal anticipatory solution for probabilistic min spanning tree.

Proof. Recall that by ( 17), E(G, T ) = v i ∈V \{v 1 } C i where C i is given by [START_REF] Jaillet | A priori solution of a traveling salesman problem in which a random subset of the customers are visited[END_REF]. Observe now that, if the vertices of T are numbered in a dfs order (starting from the root) and if the set A(v i ) of the ancestors of a vertex v i in T is exactly the set A(v i ) = {v 1 , v 2 , . . . , v i-1 }, then C i can be written as:

C i = i-1 j=1 p i p j d ij i-1 l=j+1 (1 -p l ) (20)
Since the star T is a minimum spanning tree, it holds that, for any vertex i, d 1i d ij , for every j = 1, i. Hence,

C i p i × d 1i × i-1 j=1 p j i-1 l=j+1 (1 -p l ).

If we denote by C T

i the contribution of vertex v i in the functional E(G, T ) of the star T , then, for every i, C T i = p i × d 1i . So, in order to complete the proof of the proposition, we have to show that, for any v i ∈ V , C T i C i , where C i refers to every other spanning tree of G. For this, it suffices to prove that:

i-1 j=1 p j i-1 l=j+1 (1 -p l ) 1 (21)
We show ( 21) by induction on i. For i = 2, the lefthand side of ( 21) is equal to p 1 = 1, so the inequality claimed is true. Suppose it true for i = n, i.e.:

n-1 j=1 p j n-1 l=j+1 (1 -p l ) 1 (22)
Then, at range n + 1 it holds:

n j=1 p j n l=j+1 (1 -p l ) = n-1 j=1 p j n l=j+1 (1 -p l ) + p n = n-1 j=1 p j n-1 l=j+1 (1 -p l ) × (1 -p n ) + p n = (1 -p n ) × n-1 j=1 p j n-1 l=j+1 (1 -p l ) + p n (22)
(1

-p n ) + p n = 1
The proof of the proposition is now completed. Unfortunately, in the case where optimal solution for min spanning tree is a path, optimality of such a solution for probabilistic min spanning tree cannot be derived as previously in the case of stars.

v 1 v 2 v 3 • • • v n-2 v n-1 v n v 1 0 1 2 • • • 2 2 2 v 2 1 0 1 • • • 2 2 2 v 3 2 1 0 • • • 2 2 2 . . . . . . . . . . . . • • • . . . . . . . . . v n-2 2 2 2 • • • 0 1 K v n-1 2 2 2 • • • 1 0 1 v n 2 2 2 • • • K 1 0
Table 1: The adjacency matrix of a graph G where optimal solutions for min spanning tree and probabilistic min spanning tree do not coincide.

Indeed consider a complete graph G, the adjacency matrix of which is given in Table 1 and its vertex-probability system is (1, p . . . , p), with p < (K -2)/(K -1) and K n. Optimal min spanning tree-solution in G is unique and is the path P = (1, 2, . . . , n -1) with value n -1.

The functional E(G, P ) of path P is E(G, P ) = (2n -3)p + (K -n)p 2 -(K -2)p 3 . On the other hand, the unique optimal anticipatory solution for probabilistic min spanning tree is the tree T * of Figure 10 with functional's value E(G, T * ) = (2n -3)p + (2 -n)p 2 + p 3 < E(G, P ), when p < (K -2)/(K -1).

probabilistic metric min spanning tree

In this section, we study probabilistic metric min spanning tree problem, that is probabilistic min spanning tree in metric complete graphs, i.e., in complete graphs whose edgeweights satisfy the triangular property that can be expressed as follows: if The optimal solution of the graph of Table 1.

(v i , v j , v k ) is a K 3 in G,
Note that, as it can be seen from the proof of Proposition 3, it does not apply in the case of metric graphs. Indeed, the complexity status of probabilistic metric min spanning tree remains open, even if we feel that this variant is also NP-complete. In what follows we give approximation results for the general case of probabilistic metric min spanning tree as well as for a natural subcase, namely probabilistic min spanning tree 1,2, where edge weights are either 1, or 2.

We denote by T and T * a tree computed by Kruskal's algorithm (i.e., a minimum spanning tree of G) and an optimal anticipatory solution for probabilistic metric min spanning tree (under CLOSEST_ANCESTOR), respectively, and we assume that they are represented as sets of edges. Observe also that, by the metric property the weight of any edge of G is smaller than the weight of any spanning tree of G and a fortiori than the weight m(G, T , CLOSEST_ANCESTOR) = opt(G) of T . Indeed, let (v i , v j ) be any edge of G, T some spanning tree of G and P (v i , v j ) be the unique path from v i to v j in T . According to the metric hypothesis, d ij w(P (v i , v j )) m(G, T ), where w(P (v i , v j )) is the weight of the path P (v i , v j ). In what follows, given a set Q of (weighted) edges, we denote by w(Q) its total weight.

General metric case

The average approximation ratio of a minimum spanning tree

For any

V i ⊆ V , we set G i (V i , E i ) = G[V i ]. Let T *
i and Ti be the spanning trees on G i resulting from the application of strategy CLOSEST_ANCESTOR on T * and T , respectively. Set

r(G i ) = m(G i , Ti )/m(G i , T * i ) and E(r) = V i ⊆V Pr[V i ]r(G i )
. Quantity E(r) is indeed the average approximation ratio of a minimum spanning tree for probabilistic metric min spanning tree. Proposition 6. E(r) (n + 2)/4.

Proof. Fix an induced subgraph G i of G and let T ∩ Ti = S. Edges of S are part of an optimal spanning tree on G and thus, they are also part of an optimal spanning tree of G i . Indeed, revisiting the proof of optimality of Kruskal's Algorithm, one can see that a tree T is a minimum spanning tree on G, iff all the edges of T are of minimum weight in at least one cut of G. Applying this to probabilistic min spanning tree, any edge e belonging to S is of minimum weight in at least one cut of G; thus, e is also of minimum weight in one cut in any subgraph G i (provided that e appears in G i ) and, therefore, it belongs to a minimum spanning tree in all the subgraphs of G where it is present.

Discussion just above leads to:

m (G i , T * i ) (23)
The edge-set Ti \ S is the set of the edges used by CLOSEST_ANCESTOR to reconnect the S. As observed in the beginning of Section 4.3, the weight of each edge of Ti \ S is smaller than, or 16 equal to, m(G i , T * i ), so:

w Ti \ S Ti \ S m (G i , T * i ) (24)
Combining ( 23) and ( 24), we get:

r i = m G i , Ti m (G i , T * i ) 1 + Ti \ S (25)
The quantity | Ti \ S| is, as mentioned above, the number of edges inserted by CLOSEST_ANCESTOR to reconnect S, but it also represents the number of vertices present in G i , but whose fathers in T (assumed rooted at v 1 ) are absent from G i . For each vertex of T except for those directly connected to the root v 1 , the probability to be present in G i but not its father is p(1 -p).

Obviously, for the vertices directly connected to the root, this probability is 0. In order to count the number of edges in Ti \ S, one can consider a set of n -1 -X Bernoulli trials (where X is the number of vertices directly connected to v 1 in T ), with a probability of success p(1 -p), each success adding an edge to Ti \ S. In this way, | Ti \ S| is a random variable following a binomial law, so one can directly compute its expectation:

Ti \ S ∼ B (n -1 -X, p(1 -p)) E Ti \ S = (n -1 -X)p(1 -p) (26)
Summing [START_REF] Murat | A priori optimization for the probabilistic maximum independent set problem[END_REF] for each G i , we derive: E(r) 1 + E(| Ti \ S|) and combining it with [START_REF] Murat | The probabilistic minimum vertex-covering problem[END_REF], we can easily get:

E(r) 1 + (n -1 -X)p(1 -p) X 1 n 4 + 1 2 = n + 2 4 as claimed.

The approximation of probabilistic metric min spanning tree

Revisit for a while the proof of Proposition 6 in Section 4.3.1.1. Notice that w(S) opt(G) and that the weight of the edge-set Ti \ S satisfies w( Ti \ S) | Ti \ S| opt(G). So, performing the same analysis and replacing T * i with T * , we finally get:

E G, T opt(G) 1 + (n -2)p(1 -p) (27)
Combination of ( 27) and ( 15) immediately leads to:

E G, T E (G, T * ) 1 + (n -2)(1 -p) (28)
In the same spirit of the analysis of Christofides' algorithm ( [START_REF] Christofides | Worst-case analysis of a new heuristic for the traveling salesman problem[END_REF]), consider now a left-to-right dfs ordering of the vertices of T , the non-elementary path produced by this dfs traversal of T and observe that in this traversal any edge is encountered at most twice. This path can be transformed into an elementary Hamiltonian path T ′ by using suitable shortcuts as shown in Figure 11(b) where these shortcuts are the boldfaced lines (edges) [START_REF] Bertsimas | A priori optimization[END_REF][START_REF] Bianchi | Local search for the probabilistic traveling salesman problem: correlation to the 2-p-opt and 1-shift algorithms[END_REF], [START_REF] Bourgeois | Probabilistic coloring of bipartite and split graphs[END_REF][START_REF] Butelle | Contribution à l'algorithmique distribuée de contrôle : arbres couvrants avec et sans contraintes[END_REF], (9, 10), [START_REF] Chazelle | A minimum spanning tree algorithm with inverse-ackerman type complexity[END_REF][START_REF] Cheriton | Finding minimum spanning trees[END_REF], [START_REF] Christofides | Worst-case analysis of a new heuristic for the traveling salesman problem[END_REF][START_REF] Cormen | Introduction to Algorithms[END_REF] and the whole path T ′ is simply the path (i, i + 1), i = 1, . . . , 12 (vertices of T in Figure 11(a) are numbered in a left-to-right dfs order). By the metric property and the dfs numbering of the vertices of the tree, the weight of a shortcut (i, j), i < j, is bounded above by the total weight of the path of T that starting from i "climbs" the tree up to the lowest common ancestor k of i and j and then goes down to j. With respect to this shortcut, edges of the path from k to i will count at most twice in T ′ (either as real edges of T ′ , or for shortcut's bound). Furthermore, they will not further be encountered in any other shortcut. In Figure 11(b), the small lines crossing an edge of T indicate the number of times this edge encounters in T ′ . So, since T ′ is also a spanning tree for Since T ′ is a Hamiltonian path having the omnipresent vertex v 1 as one of its endpoints, any modification of it by the modification strategy CLOSEST_ANCESTOR due to the absence of any subset V i ⊆ V , will produce a path T ′ i that always remains Hamiltonian for the graph

G: m G, T ′ 2 opt(G) (29)
G ′ i = G[V \ V i ]
. By the metric hypothesis, for any

V i ⊆ V : m G ′ i , T ′ i m G, T ′ (30)
Then, the functional associated with T ′ can be written as:

E G, T ′ = V i ⊆V Pr [V \ V i ] m G ′ i , T ′ i (30) m G, T ′ × V i ⊆V Pr [V \ V i ] (31)
= m G, T ′ (29)
2 opt(G) (15)

2 p × E (G, T * ) (32)
So, T ′ is a (2/p)-approximation for probabilistic metric min spanning tree and taking the best (with respect to the functional) among T and T ′ , the following result holds (according to [START_REF] Th | Steiner forests on stochastic metric graphs[END_REF] and [START_REF] Tarjan | Efficience of a good but not linear set-union algorithm[END_REF] and concludes this subsection.

Proposition 7. probabilistic metric min spanning tree is approximable in polynomial time within ratio bounded above by min{1 + (n -2)(1 -p), 2/p}.

probabilistic min spanning tree 1,2

We now focus on a particular but natural and well-studied class of metric complete graphs where edge weights are either 1 or 2. It is easy to see that any such graph is metric. We first prove the following easy approximation result for probabilistic min spanning tree 1,2 that will be subsequently improved. Proposition 8. A minimum spanning tree of G is a (2 -p)-approximation for probabilistic min spanning tree 1,2.

Proof. Consider a minimum spanning tree T of G computed, for instance, by Kruskal's algorithm. Then, the following fact holds.

Fact 1. If T has k edges of weight 2, then in E(G, T * ), (i.e., the optimal value for probabilistic min spanning tree 1,2 under CLOSEST_ANCESTOR) there exist at least k vertices with contribution 2p (recall that by [START_REF] Jaillet | Probabilistic traveling salesman problem[END_REF], the functional can be defined as the sum of the contributions of the vertices, each such contribution expressed by ( 20)).

Indeed, if T has k edges of weight 2, then, by construction of T , there exist k + 1 distinct connected components V i in the graph G ′ (V, E ′ ) (that contains only edges of G of weight 1); edges between any two vertices of any two of these components have weight 2 (suppose, w.l.o.g., that the omnipresent vertex v 1 belongs to V 1 ). So, the following holds:

∀i ∈ {1, . . . , k + 1}, ∀v j ∈ V i , v k / ∈ V i , d jk = 2 (33)
Assume now a bfs on T , starting from v 1 and denote by u i the first-visited vertex of V i (obviously, u 1 = v 1 ). For every i > 1, all the vertices visited before u i (a fortiori those on the path from v 1 to u i ), do not belong to V i ; hence, by (33), every edge linking u i to any of these vertices has weight 2. So, for i = 2, . . . , k + 1, the contribution

C(u i ) of u i to E(G, T ) is 2p.
Discussion above holds for any spanning tree of G and a fortiori for T * ; hence, truth of Fact 1 is immediately derived.

As a consequence of the discussion above, T * has at least k vertices with contribution 2p to the functional; observe furthermore that the contribution of any of the other n -k -1 vertices (recall that vertex v 1 has null contribution) is at least p. So:

E (G, T * ) 2p × k + (n -k -1) × p = p × (n -1 + k) (34)
Revisit now T and consider that a vertex is "covered" by the edge of T entering it in the bfs visiting. Based upon the discussion above, there are k vertices covered by edges of weight 2 and n -k -1 vertices covered by edges of weight 1. Consider a vertex w covered by an edge of weight 1. It is easy to see from (20) that its contribution C(w) is at most p(2 -p) (considering that all the other edges incident to it in G have weight at most 2). So:

E G, T p × (2 -p) × (n -1 -k) + 2pk = p(n -1) × (2 -p) + p 2 × k (35)
Combining ( 34) and ( 35) we get after some easy algebra:

E(G, T )/E(G, T * ) 2-p as claimed.
In what follows we refine the result above. For this we consider an execution of Kruskal's algorithm that starts by introducing in the tree all the edges of weight 1 incident to the vertex v 1 . Let us denote by T spanning tree so constructed; notice that T is a minimum spanning tree for G. Proposition 9. The tree T approximates T * within ratio:

1 + (2 -p)(n -2) n -1 + (1-p) 2 -(1-p) n p
Proof. Recall that, by Proposition 8, if the value of a minimum spanning tree T is equal to n + k then, for every spanning tree T there exist at least k (exactly k for T ) vertices each contributing with 2p to the functional associated with T . For simplicity, assume that this number is exactly k for T also (if not, i.e., if we have more than k such vertices, the bounds derived below are even better). Among the remaining (less than) n -1 -k vertices of T let us denote by n 1 the number of those that in G are connected to v 1 by edges of weight 1 and by U 2 the set of those that in G are connected to v 1 by edges of weight 2; set finally

n 2 = |U 2 |. Obviously, n -1 = n 1 + n 2 + k.
Consider a vertex v i ∈ U 2 , suppose that its height is i and recall that, by definition, d i1 = 2. Then, the contribution C i of v i (see also [START_REF] Jaillet | The probabilistic vehicle routing problem[END_REF]) in E(G, T ) is at least:

C i p 1 + (1 -p) i-1 (36)
where in (36) it has been assumed that only edge (v 1 , v i ) has weight 2, while every other edge on the path from v 1 to v i in T has weight 1. Number the vertices of T as they appear in a bfs ordering of T and let ℓ 1 , ℓ 2 , . . . , ℓ n 2 be the bfs numbers of the vertices of U 2 . Fix a vertex v i ∈ U 2 with bfs number, say, ℓ i and notice that the n 2 -i vertices of U 2 numbered ℓ i+1 , . . . , ℓ n 2 all height at least equal to the height of v i . The height of v i is at most n -1 -(n 2 -i) = n -1 -n 2 + i; hence, (36) becomes:

C i p 1 + (1 -p) n-n 2 +i-2 (37)
Using (37) and denoting by C(U 2 ) the total contribution of the vertices of U 2 in E(G, T ), we get:

C (U 2 ) n-1 i=n-n 2 p × 1 + (1 -p) i-1 = pn 2 + p × n-1 i=n-n 2 (1 -p) i = p × n 2 + (1 -p) n-n 2 -(1 -p) n p (38)
What it has been discussed until now holds for any spanning tree T , a fortiori for the optimal anticipatory tree T * . So, using (38), the functional E(G, T * ) becomes:

E (G, T * ) p × n 1 + p × n 2 + (1 -p) n-n 2 -(1 -p) n p + 2p × k (39)
On the other hand, consider the tree T and recall that, by its construction, n 1 of its vertices are directly linked to v 1 . Then, their contribution to E(G, T ) is equal to pn 1 . According to the proof of Proposition 8, the contribution of any of the n 2 vertices linked in G to v 1 by edges of weight 2 but covered in T by edges of weight 1 is at most p(2 -p) and the contribution of any of the remaining k vertices (covered in T by edges of weight 2) is 2p. Putting all this together, we derive:

E G, T p × n 1 + p(2 -p) × n 2 + 2p × k (40)
Combining ( 39) and (40) we get:

E G, T E (G, T * ) p × n 1 + p(2 -p) × n 2 + 2p × k p × n 1 + p × n 2 + (1-p) n-n 2 -(1-p) n p + 2p × k (41) n 1 + (2 -p) × n 2 n 1 + n 2 + (1-p) n-n 2 -(1-p) n p (42) n 1 + (2 -p) (n -1 -n 1 ) n -1 + (1-p) n 1 -1 -(1-p) n p 1 + (2 -p)(n -2) n -1 + (1-p) 2 -(1-p) n p ( 43
)
where the rightmost expression of (42) is due to the fact that ratio's expression is decreasing with k 0, the first expression of ( 43) is due to the fact that since k is set to 0, n -1 = n 1 + n 2 and the second expression of ( 43) is due to the fact that the first expression is decreasing with n 1 but k and n 1 cannot be simultaneously equal to 0 (if n 1 = 0, then no vertex of G is linked to v 1 with an edge of weight 1, so k 1), hence, n 1 1. This proves the ratio claimed. For tightness, consider the graph of Figure 12. There, ∀i ∈ {3, . . . , n}, d 1i = 2; every other edge has weight 1. So, any tree where v 1 is linked to v 2 is a tree T , potentially built by an execution of Kruskal's algorithm as that considered in the proposition. For instance, such a tree can be the tree of Figure 13(a). It is easy to see that the value of the functional of this tree is equal to p(1 + (2 -p)(n -2)). On the other hand, the optimal anticipatory solution T * is shown in Figure 13(b); the value of the functional associated with T * is equal to p

v 3 v 4 v 5 v n-2 v n-1 vn v 2 v 1 2 2 2 2 2 2
(n -1) + p n-2 i=1 (1 -p) i = p(n -1) + ((1 -p) -(1 -p) n-1
). can see that when p is fixed (i.e., independent on n), the approximation ratio achieved is strictly better than 2. On the other hand, when p ∼ 1/n, then since lim n→+∞ (1 -p) n /p = n/e, the ratio claimed in Proposition 9 tends to 1.225, for large values of n. If p ∼ 1/n k , k > 1, then for large values of n, this ratio tends to 1. Finally, if p ∼ 1/n k , k < 1, then (always for large values of n) the ratio is asymptotically equal to 2.

probabilistic min spanning tree under modification strategy ROOT

We will now analyze probabilistic min spanning tree under another modification strategy. In this strategy, denoted by ROOT, present vertices whose fathers are absent are connected to the omnipresent root (see Figure 14 for an example). Clearly, its complexity is O(n). ROOT is very natural in terms of network design where, for instance, in case of failure of intermediate servers, surviving servers are connected to the central one in order to ensure total global connectivity of the remaining network.

The complexity of probabilistic min spanning tree

With respect to ROOT, the contribution C i of a vertex v i can be written as follows:

C i = C (v i , T ) = p i p f (i) d i,f (i) + 1 -p f (i) d i,1
where v f (i) is the father of v i in T . As previously, summing the C i 's, for each vertex of the graph, leads to the functional associated with the strategy ROOT:

E(G, T ) = v i ∈V p i p f (i) d i,f (i) + 1 -p f (i) d i,1 (44)
The value of E(G, T ) can be computed in polynomial time. We will now show that probabilistic min spanning tree under ROOT belongs to P, by specifying a polynomial algorithm that solves this problem optimally.

Proposition 10. probabilistic min spanning tree under ROOT can be optimally solved in polynomial time.

Proof. Transform the initial graph G(V, E) into a directed one G d (V, A) having the same vertexset as follows: for each edge (v i , v j ) of E (i, j = 1), add two arcs (v i , v j ) and (v j , v i ) in G d with weights:

d ′ i,j = p i (p j d i,j + (1 -p j ) d i,1 ) d ′ j,i = p j (p i d j,i + (1 -p i ) d j,1 )
and for each edge (v 1 , v i ) of E, add one arc (v 1 , v i ) in G d with the same weight. Note that the number of arcs in G d is at most 2|E|. Run in G d Edmonds' polynomial algorithm for the arborescence problem ( [START_REF] Edmonds | Optimum branchings[END_REF][START_REF] Georgiadis | Arborescence optimization problems solvable by edmonds' algorithm[END_REF][START_REF] Korte | Combinatorial optimization: theory and algorithms[END_REF]; this problem consists of finding a minimum-weight spanning tree in a directed graph), taking v 1 as root. It returns a rooted tree of minimum total edge-weight spanning all the vertices of G d . This algorithm consists of determining the minimum weight arc entering each vertex (except for the root), and adding this edge to the solution. At this point, the solution has n-1 arcs, but may contain loops. If the solution does not contain loops, then it is an optimal arborescence, otherwise loops are successively broken in an optimal way. Retain this tree as anticipatory solution for G (simply delete orientations of arcs and unify the so obtained duplicate edges). Given the edgeweight function defined in G d , this tree also minimizes the functional E(G, T, ROOT), i.e., it is optimal for probabilistic min spanning tree.

Stability of the solutions

Same probabilities for all vertices

We first focus on the case where all vertices have the same presence-probability, p (except for v 1 which still has probability 1). We show that in such graphs, the deterministic and probabilistic solutions coincide, which is not true anymore when probabilities are distinct.

Proposition 11. Let G be an instance of probabilistic min spanning tree problem under strategy ROOT, where all vertices, except for the root, have the same probability p. On such an instance, the optimal tree T and optimal a priori tree T * coincide.

Proof. In an instance where all vertices are equiprobable, the general functional formula given in (44) can be reformulated as follows:

E(G, T ) = v i ∈V p pd i,f (i) + (1 -p) d i,1 (45)
In this case, notice that the second member of the sum does not depend on the structure of the tree. Thus, one can rewrite the functional as:

E(G, T ) = p   (v i ,v j )∈T pd i,j + v j ∈V (1 -p) d 1,j   (46)
The first term in the parentheses of (46) is p times the value of the spanning tree T , while the second term is the weight of the star rooted at v 1 (that is constant for a given graph), i.e.:

E(G, T ) = p (pd (T ) + (1 -p) d (S)) (47)
So, in order to minimize E(G, T ) in (47), it suffices to minimize d(T ).

Star as deterministic solution

Let us now consider the particular case where the anticipatory solution is a star rooted at v 1 .

Then, the following result holds.

Proposition 12. Let T be a star rooted at v 1 . If T is an optimal solution for min spanning tree then it is also an optimal anticipatory solution for probabilistic min spanning tree under ROOT.

Proof. Consider G d as it has been built in the proof of Proposition 10. If the optimal solution for min spanning tree in G is a star, then:

∀i, j = 1, d 1,j d i,j (48)
According to the definition of the edge-weight function d ′ in G d , it can be easily seen that the property expressed by (48) extends also to G d : ∀i, j = 1, d ′ 1,j d ′ i,j . Since edges of G incident to v 1 are not duplicated when they become arcs in G d , in the case of stars rooted at v 1 the minimum-weight arc for each vertex v i will be the arc (v 1 , v i ) and no loop will appear. Thus, in this case, the probabilistic optimum is the same star.

ROOT vs. CLOSEST_ANCESTOR

It has been shown that ROOT leads to a probabilistic model much easier to analyze and optimize than that induced by CLOSEST_ANCESTOR. But the optimum returned by the former might not be as good in terms of expected value as that returned by CLOSEST_ANCESTOR. Naturally, the choice between ROOT and CLOSEST_ANCESTOR will depend on the real world application so-modeled. But still, even if probabilistic min spanning tree under ROOT is polynomial, comparing these two strategies in terms of quality of their respective returned solutions seems to be interesting and adds some further insight to the apprehension of the multiple difficulties occurring when handling probabilistic problems. Proposition 13. Let E(G, T * R ) and E(G, T * CA ) be the expected values of optimal anticipatory optima associated with ROOT and CLOSEST_ANCESTOR, respectively. Even in metric graphs, the approximation ratio between these two values is unbounded.

Proof. Let us consider a graph G of order n, ordering on its vertices and assume that the optimal solution for min spanning tree is a path. In this graph, vertices are equiprobable and weights are as follows:

d 1,i = n + i -1 ∀i = 1 d i,j = j -i ∀i, j 1 < i < j n (49)
It can be easily seen that such graph is metric and that the path P = (v 1 , v 2 , . . . , v n ) is a minimum spanning tree (see Figure 15 for an example with n = 5).

From Proposition 11, P is also the optimal anticipatory solution for probabilistic min spanning tree under ROOT, since vertices are equiprobable. The weight of P is 2n -1. So, revisiting (47), its expected value is: Consider now P as the anticipatory solution for CLOSEST_ANCESTOR. Recall that this strategy reconnects each vertex to its closest present ancestor, so that, in G, any adjusted tree will be a path, with weight at most d(P ) = 2n -1. Figure 16 illustrates this assumption and depicts all the paths generated by CLOSEST_ANCESTOR, each of which has weight at most 2n -1 = 7. Thus, a loose (but sufficient) lower bound for E(G, T * CA ) is:

E (G, T * R ) = p   p(2n -
E (G, T * CA ) 2n -1 (51)
Combining ( 50) and (51), we finally get for the ratio between the expected values associated with these two strategies:

E (G, T * R ) E (G, T * CA ) p 2 + p(1 -p)(n -1) 1 + n 2 2n -1 (52)
that is O(n) for large values of n when p is constant. In other words, there exist graphs where the expected value of the optimum with respect to ROOT is much larger than the expectation for CLOSEST_ANCESTOR when applied to this solution.

Conclusion

In this paper we have handled the probabilistic min spanning tree problem in the framework of probabilistic combinatorial optimization. We have proposed two fast modification strategies (CLOSEST_ANCESTOR and ROOT) for reconstructing a second-stage tree and we have studied particular cases of anticipatory solutions. We have shown that the problem of optimizing the expectation of the second-stage cost by selecting an appropriate first-stage (anticipatory) solution is NP-hard under strategy CLOSEST_ANCESTOR while it is polynomial under ROOT. Under CLOSEST_ANCESTOR strategy we have given several approximation results for probabilistic metric min spanning tree and probabilistic min spanning tree 1,2.

There are several open questions subject for further research. To our opinion, the major among them are the complexities of probabilistic metric min spanning tree and probabilistic min spanning tree 1,2 (under CLOSEST_ANCESTOR; we conjecture that they are both NP-hard) and the improvement of their approximation ratios.

Figure 1 :

 1 Figure 1: An anticipatory spanning tree T and its adjustment.

Figure 1 (

 1 Figure1(b) gives an example of how strategy CLOSEST_ANCESTOR works starting from an initial tree T shown in Figure1(a) and assuming that vertices 3, 5, 6, 9, 13 and 16 are absent from V ′ .Our goal in this section is to study the following problem: find an algorithm for taking "good" a priori decisions, i.e., that determines a spanning tree T * , that optimizes E(G, T ) under modification strategy CLOSEST_ANCESTOR ; this is probabilistic min spanning tree (under strategy CLOSEST_ANCESTOR). In what follows, we show that this problem is NP-hard in general complete graphs with p 1 = 1. We then study approximation of this problem in metric graphs as well as in a particular subclass of them where edge-weights are either 1 or 2. The approximation ratio is defined as E(G, T )/E(G, T * ).

Figure 2 :

 2 Figure 2: An example for the reduction from 3 exact cover to probabilistic min spanning tree.

Figure 4 :

 4 Figure 4: The "interesting" subgraph of G.

5 Figure 5 :

 55 Figure 5: 5 out of 16 trees spanning component of Figure 4 . . .

10 Figure 6 :

 106 Figure 6: . . . other 5 out of 16 trees spanning component of Figure 4 . . .

14 Figure 7 :

 147 Figure 7: . . . other 4 out of 16 trees spanning component of Figure 4.

16 Figure 8 :

 168 Figure 8: . . . and the last 2 out of 16 trees spanning component of Figure 4.

  then d ab d ac + d bc , for any permutation (a, b, c) of {i, j, k}.

1 n - 2 nFigure 10 :

 1210 Figure10: The optimal solution of the graph of Table1.

Figure 11 :

 11 Figure 11: A tree T and the Hamiltonian path T ′ produced from it.

Figure 12 :Figure 13 :

 1213 Figure 12: A graph where the ratio claimed in Proposition 9 is tight.

  An initial tree T . . .

Figure 14 :

 14 Figure 14: An anticipatory spanning tree T and its adjustment.

Figure 15 :

 15 Figure 15: A graph G with n = 5.

Figure 16 :

 16 Figure 16: An anticipatory solution P and all its possible adjustments.

* Research supported by the French Agency for Research under the DEFIS program TODO, ANR-09-EMER-010.


T Poglio

E Savaria
email: eric.savaria@space.alcatel.fr

L Wald

OSIRIS: A SIMULATOR OF OUTDOOR SCENES IN THERMAL INFRARED RANGE

Keywords: Imagery, Landscape, Modelling, Remote Sensing, Temperature, Three-Dimensional

This paper deals with the simulation of very high spatial resolution images in the thermal infrared range, from 3 to 14 µm. It recalls the physical processes occurring in this spectral range. The complexity of the simulation of such processes is explained. The specifications of the simulator and a methodology for the simulation of infrared imagery are proposed. This methodology enables a very accurate simulation of the signal coming from each object constituting the landscape. The interactions between the radiations and objects and the convective and conductive interactions between objects themselves are considered. Their variations in time, and the recent past of the temperature and the humidity for each object, are taken into account. To reproduce these physical phenomena, the computation is performed on elements, which are defined as homogeneous entities with respect to the physical processes. The architecture of the simulator OSIRIS using the elements is presented. Finally, examples are shown, showing the efficiency of the simulator and the methodology used.

INTRODUCTION

There is a growing concern of very high spatial resolution imagery in the infrared range from 3 to 14 µm. Simulators of landscapes in thermal infrared range need to be developed. One of the major points in the simulation is the accurate knowledge of the input parameters, and particularly the accurate knowledge of the scene to be observed. Synthesis approaches to outdoor scenes offer the possibilities to simulate changing meteorological conditions, different places, different landscapes, different times and different spectral bands.

As physical processes play an essential part in the signal coming from the scene, there is a need for research on spatial, spectral and temporal properties of natural and human-formed objects, their image signatures and their modelling. The synthesis of outdoor scenes in the infrared range is at the crossings of computer vision, physics and remote sensing.

In thermal infrared, the flux coming from an object is partly emitted by the object because of its own temperature, and partly due to the reflection of incident rays on the surface of this object. Depending on the surface material and the spectral band, emission or reflection process dominates the signal. For each object in the scene, the landscape simulator predicts the heat exchanges between objects, the temporal evolution of heat balance, the surface temperature, the spectral emission and the spectral reflection of all incident fluxes. Such a simulator takes into account 3-D landscape description, environmental conditions, thermal and optical characteristics of the objects, and the spectral band of the sensor.

Jaloustre-Audouin (1998) and [START_REF] Jaloustre-Audouin | Simulated images of outdoor scenes in infrared spectral band[END_REF] have developed a simulator of any type of landscape in 2-D in the infrared band. Image simulators taking into account a 3-D representation of the landscape as input exist, but they are for visible range or dedicated to specific applications. For example, [START_REF] Thirion | Realistic 3-D simulation of shapes and shadows for image processing[END_REF] has developed a simulator of high spatial resolution image in the visible range. [START_REF] Johnson | MuSES: A new heat and signature management design tool for virtual prototyping[END_REF] have developed a simulator in the infrared range to simulate the behaviour of vehicles. [START_REF] Guillevic | Modélisation des bilans radiatif et énergétique des couverts végétaux[END_REF] was interested in radiative budget modelling for vegetation canopy studies. [START_REF] Barillot | ONERA DOTA[END_REF] has developed MISTRAL, which can simulate an image taking into account a 3-D description of the landscape. A simulator of landscape adapted to remote sensing applications does not exist and has to be developed. It should take into account a 3-D description of the scene with high spatial resolution.

Physical processes occurring in the signal coming from the scene are described in the following section. Next, the specifications of the simulator are given. The main difficulties, related to these specifications and the infrared range are explained. A new methodology is proposed for the simulation of very high-resolution 3-D scenes and the consequences on the landscape modelling are explained. Section 4 details the architecture of the simulator using this modelling; each subpart of the simulator is presented, and its operation is explained. Finally, section 5 presents examples of synthesised scenes.

PHYSICAL PROCESSES OCCURRING IN THE INFRARED RANGE

The radiance balance equation

In the general case, the energy equilibrium for a set of radiating objects is expressed, independently on the wavelength λ, by the following equation:

( ) ( ) v v e v v x L x L ϕ θ ϕ θ , , , , = ( ) ( ) ∫ Ω + ω θ ϕ θ ϕ θ ϕ θ d x L x f j v v r cos , , , , , , (1)
Notations and definitions used here are those given by Sillion and Puech (1994). Additional information on transfer in global illumination can be found in [START_REF] Arvo | Transfer equation in global illumination, Global illumination[END_REF].

• L(x,θ,ϕ), L e (x,θ v ,ϕ v ) and L j (x,θ,ϕ) are respectively the radiance leaving point x in the viewing direction (θ v ,ϕ v ), the emitted radiance by point x in the same direction, and the incident radiance impinging the point x from direction (θ,ϕ). • Ω is the set of directions (θ,ϕ) in the hemisphere covering the surface at point x.

• f r (x,θ,ϕ,θ v ,ϕ v ) is the bidirectional reflectance distribution function (BDRF) describing the reflective properties of point x [START_REF] Nicodemus | Geometrical considerations and nomenclature for reflectance[END_REF].

Both emitted and incident radiance, the BRDF, and the response g of the instrument depend on the wavelength λ.

BRDF models exist in the visible range [START_REF] Rusinkiewicz | A survey of BRDF representation for computer graphics[END_REF]. They usually depend on about five parameters that can be found in databases such as Columbia-Utrecht (2001). Both models and databases are nor assessed in the infrared range. For the sake of concision, we assume lambertian reflectors and emitters, and the isotropy of the BRDF. Considering fluxes G, E, and B j instead of radiance L, L e and L j , and expressing the environment of the object i, the previous equation becomes:

( ) ( ) ( ) ( ) ( ) ∑ ∫ ∫ = + = N j j i ij i i d B g F d E g G 1 , , 2 1 2 1 2 1 λ λ λ λ λ λ λ λ λ ρ λ λ λ λ (2)
F ij is the form-factor and represents the rate of energy exchange between object i and object j. It can be computed [START_REF] Schröder | On the form factor between two polygons[END_REF] or estimated [START_REF] Wallace | A ray tracing algorithm for progressive radiosity[END_REF]. Due to spectral quantities and integral equations, the radiosity method [START_REF] Foley | Computer Graphics, Principles and Practice[END_REF][START_REF] Watt | [END_REF] cannot be used easily, except in considering many systems of equations: one system per spectral sample in a given spectral range. Nevertheless, under useful simulation conditions, the number of neighbours N is generally small as well as the form-factor. The previous equation is solved with an iterative method, considering emission and reflection at order k. Equation (2) will be used to compute spectral radiance leaving objects. Radiosity method can be applied when equation ( 2) is integrated from zero to infinity, to compute energy flux balance impinging objects.

The prediction of emitted flux and of the temperature

The main difficulty related to equation ( 2) is to compute the E i terms that correspond to the self-emission of the object. They can be expressed as the product of the emissivity ε s of the object by the blackbody function L bb at temperature T s . For lambertian emitters, it comes:

( ) ( ) ( ) λ λ ε π λ , s bb s i T L E ⋅ = (3)
The surface temperature of the object has to be known to make the simulation. This temperature is governed by the heat equation, which can be written under thermodynamical conditions usually encountered in landscapes:

T t T ∆ ⋅ = ∂ ∂ κ ( 4
)
where κ is the thermal diffusivity, and ∆ is the Laplacian operator. This equation may be solved using e.g. the finite difference method or the method proposed by [START_REF] Deardorff | Efficient prediction of ground surface temperature and moisture with inclusion of a layer of vegetation[END_REF].

Because of thermal inertial, the knowledge of this temperature at t requests the temperature at the previous moment (t-dt). The in-depth temperature of the object, and the energy flux balance at the surface of the object are the two boundary conditions required to solve a second-order differential equation. Given an initial state, an iterative process is harnessed to compute surface temperature at the instant of simulation. The interactions between physical parameters, and their variations in time are modelled. Methods exist to compute these interactions and their changes in time [START_REF] Johnson | A methodology for rapid calculation of computational thermal models[END_REF][START_REF] Jaloustre-Audouin | Simulated images of outdoor scenes in infrared spectral band[END_REF]. Because it is iterative, and because of the complexity of models used for the energy flux balance determination, this process is by far the more demanding in computation time of all the simulation processes.

METHODOLOGY USED FOR THE SYNTHESIS

Specifications

In the infrared range, the spectral flux coming from an object depends upon the meteorological conditions existing in the scene: surface temperature, air temperature, humidity of the object, humidity of the atmosphere… and the optical properties of the object itself in the considered spectral range. To perform a simulation, four types of inputs are provided to the simulator:

• the 3-D landscape geometrical description. The landscape is expressed as a set of located and oriented objects, having their own surrounding. Each object is made of several facets, each of them made of the same material, • the set of the conditions of the simulation for the present time and past hours: day, time, place, sky cloudiness…,

• a database of thermal and optical characteristics of all primary materials existing in the landscape (albedo, spectral reflectance (ASTER, 2000), specific heat, thermal conductivity, roughness, leaf area index for vegetation,…),

• the spectral response of the sensor g.

Main difficulties related to infrared range

In short-wave radiation, computation is made on facets, which are flat external parts of an object. In thermal infrared range, the synthesis process requests that each point of a facet exhibits the same energy flux balance at instant t: this facet is homogeneous with respect to energy flux balance. Considering e.g. the shadow variations, this same facet will not be necessary homogeneous at t+dt, and so on. This introduces difficulties to compute temperatures. The smallest entities representing the scene may be considered, voxels for instance. With voxels, entity is either sunny or shadowed. Problems rise with respect to the number of voxels multiplied by the computation time used for energy flux balance and temperature determination for a voxel. In a similar way, geometrical facets are heterogeneous with respect to boundary conditions existing on these entities; if computed on facet, surface temperature would not be physically relevant.

Taking into account variations in time of all the interactions differentiates the image synthesis in the infrared range from that in the visible domain. The synthesis methods used for the simulation of landscapes for short wavelengths do not need to reproduce the recent past of the landscape as it is observed in real infrared images. The radiosity method can be used in such a case. In the thermal infrared range, it cannot, except for considering the radiosity method for each voxel and each timestep. An entity permitting to compute both temperatures at each instant during the process and the radiance leaving the scene has to be used.

In addition, a 3-D description of the landscape is necessary to perform a simulation with a very high spatial resolution. In this respect, objects forming the landscape interact each other. Realistic image simulation should reproduce these physical interactions between objects (Poglio et al., 2001a). This adds to the complexity of the simulation process.

The landscape representation

We defined an element as an entity that exhibits homogeneous properties with respect to geometrical considerations, material constitution, and the occurring physical phenomena at each instant (Poglio et al., 2001b). To reduce as many as possible the number of elements, and afterward the computation time, element is defined as the largest entity included in a facet.

The element is a part of an object; it is a 3-D entity. Its external surface is flat and oriented. The in-depth constitution of the element is made of one or several layers of primary materials; for instance, a wall can be made of two layers; construction concrete and insulation. The element is homogeneous with boundary conditions, both internal and external. Figure 1 illustrates the element.

To better understand the element, one may consider a facet; this facet is partly shadowed at instant t. These portions of the facet are a preliminary set of elements, which will be subsequently subdivided by taking into account other phenomena and other instants.

The mesh supporting objects constituting the landscape is made of the union of elements for the period of simulation of temperature. Figure 2 illustrates the representation of the landscape. The landscape is divided into objects, objects into facets, facets into elements. In each subdivision, properties and characteristics are inherited from the previous hierarchical level and are added to perform an element-based representation of the landscape.

k-1-3 Element k-1-2 Element k-1-1 Element k-2-5 Element k-2-4 Element k-2-3 Element k-2-2 Element k-2-1 Element k-p-1

ARCHITECTURE OF THE SIMULATOR OSIRIS

The simulator OSIRIS is divided into four primary simulators, each of them dealing with a particular sub-part of the simulation (Poglio et al., 2001c). These four primary simulators, called (S0) to (S3), operate successively.

The main technical originality of the simulator OSIRIS is the pre-processing simulator, (S0), generating the elements. The simulator (S0) operates with the following scheme (figure 3). The shadow maps are made and combined with the facet description of the scene to obtain the element-based representation. In addition, the radiative and conductive surroundings, the wind velocity for each element and the formfactor matrix are computed. All outputs and inputs of (S0) are inputs to (S1). (S1) predicts the surface temperature for each element defined by (S0). The simulator operates in an iterative way. It predicts the heat exchanges, the relative humidity, and the depth-dependent temperature for each element and for each time step (Poglio et al., 2001c). The output of (S1) is the surface temperature for each element constituting the landscape (figure 4).

Element-based representation

In-depth element mesh computation

In Then, (S2) simulates spectral emitted and reflected fluxes. Emitted flux is predicted with the help of equation ( 3) and the (S1) output; ancillary data, like the viewing direction of the scene is required here. Reflected flux computation requires the knowledge of all incident spectral fluxes, especially the sun spectral radiation and the atmospheric spectral radiation (Poglio et al., 2001c). The output of the simulator (S2) is the 3-D scene wherein the emittance of each element is known for the viewing direction (figure 5). The fourth primary simulator (S3) generates an image for a given viewing angle. Depending on the user preference, this primary simulator generates an image as it would be seen by the sensor, or an image that is only a visualisation of the 3-D scene. The first option requires another simulator to model the acquisition system, such the AS 3 -I simulator of Alcatel Space Industries. The second option offers a visualisation of the 3-D scene. It permits to see the scene without any alteration due to the acquisition system. The set of these four primary simulators constitutes the simulator OSIRIS. The user of such a simulator can be interested in not only the final images, but also in other additional outputs. The element-based representation of the scene, the surface temperature of each element and the emitted flux or the reflected flux for example, are such outputs. They can be used for the training of future users, and to relate each of the inputs and initial conditions to a change in the simulated image.

RESULTS AND DISCUSSION

The simulation presented here takes place in Amiens in France (latitude: 49.54 N, longitude: 2.18 E). Houses are made of construction concrete, and an internal thermal insulation made of polystyrene. The central area is a car park made of asphalt, and the square enclosing this park is a bare soil.

Spectral band impact

The four following images (figure 6) are simulated the 12 th of February, at 2 p.m. after a sunny day, and after shadows have scanned half of the scene. All images are viewed with a zenith angle of 30 °, and an azimuth angle of 60 ° East. Figure 6a represents the surface temperature, ranging from 0 °C in the shadows of the facades to 24 °C for sunlit exterior walls. Figure 6b is an image simulated between 3 and 5 µm. Radiance range from approximately 0.6 to 2.8 W.m -2 .sr -1 . Solar radiation dominates in the signal in this band; contrast between shadowed and sunlit areas is important. .sr -1 . The difference of contrast between the park made of asphalt and the bare soil is due to the difference of the ratio of emissivity values for those materials in these two bands. It leads to observe a higher contrast from 8 to 10 between the park and the bare soil, and a lower contrast from 10 to 12, compared to temperature image; this is due to self-emission process.

Temporal shadow effects

The following sequence of images illustrates the shadow variations during the day (figure 7). Images are simulated between 8 and 12 µm, the 21 st of June. Not only spatial influence of shadows varies during the day, but also the contrast between shaded and sunlit areas. Another typical effect in the infrared range is the remanence of shadows. Simulations exhibit continuous variations of radiometry in the areas previously shadowed. This is due to thermal inertia. In the illustration, remanence effect is emphasised on the bare soil, due to the high capacity of this material to store energy.

(a) (b) (c) (d) Figure 7: illustration of the shadow variations during the day; images are simulated between 8 and 12 µm, at 6 and 9 a.m. and at 12 and 15 p.m.

CONCLUSION

The study demonstrates that realistic representation of the landscape is only possible with a 3-D representation, as the sampling rate increases in both time and space. In this respect, objects that form the landscape interact each other. A simulator of realistic images should reproduce faithfully these physical interactions between objects. In the infrared range, the main physical phenomena affecting the signal emitted by the scene are shadow effect, wind disturbance linked to landscape relief, multiple reflections or heat conduction.

The above conclusions were used as a starting point in the specification, the design and the development of a simulator of landscapes in the thermal infrared range with a very high spatial resolution. The physical process underlying the emitted flux in thermal infrared is very complex. The recent history of the landscape is present in the simulated image. The accuracy of the models of the physical processes and their interactions should be high in order to obtain a good quality. Consequently, a new methodology has been devised to design a simulator of landscape described by a 3-D representation.

For an efficient implementation of the 3-D properties, the concept of element was defined. It permits to describe in an accurate manner the objects of the landscape with respect to the physical processes and their variations in time and interactions.

The elements are homogeneous entities with respect to geometry, material and temporal evolution of physical phenomena. The architecture of the simulator was adapted to this concept of element and to the specificity of the simulation in the thermal infrared range. The simulator is made of four primary simulators, each of them having a well-defined role with respect to the description of the landscape on the physical processes.

The present study demonstrates the relevance of such a new methodology. Unavoidably it requests considerable efforts in landscape modelling, software development and computational resources, compared to simulation in the visible range. A first version of this simulator OSIRIS was developed as a proof-ofconcept. It provides realistic images of outdoor scenes in the infrared range.

Figure 1 :

 1 Figure 1: illustration of the multi-layered in-depth constitution of an element and the homogeneity with respect to boundary conditions on both the internal and external surface.

Facet

  Figure 2: illustration of the landscape element representation.

Figure 3 :

 3 Figure 3: the detailed architecture of the simulator (S0).

Figure 4 :

 4 Figure 4: the detailed architecture of the simulator (S1).

  Figure 5: the detailed architecture of the simulator (S2).

  Figures 6c and 6d are images simulated in thermal bands, from 8 to 10 µm and 10 to 12 µm respectively. Influences of the different physical phenomena are approximately the same in these two bands. Radiance range from 12 to 18 W.m -2 .sr -1 . The difference of contrast between the park made of asphalt and the bare soil is due to the difference of the ratio of emissivity values for those materials in these two bands. It leads to observe a higher contrast from 8 to 10 between the park and the bare soil, and a lower contrast from 10 to 12, compared to temperature image; this is due to self-emission process.

The author has requested enhancement of the downloaded file. All in-text references underlined in blue are linked to publications on ResearchGate. The author has requested enhancement of the downloaded file. All in-text references underlined in blue are linked to publications on ResearchGate.

ACKNOWLEDGEMENTS

This research was performed under a grant of A.N.R.T., Ministry of Research in France. Thanks also go to J.R. Shewchuk for the use of Triangle, the 2-D quality mesh generator and Delaunay triangulator, which permits us to perform the different triangulations.