Dr Pierre Van Elslande

Motorized two-wheelers inside the traffic system: What are the key questions for enhancing road safety?

Introduction

Marginal in the past, powered-two-wheelers (PTW) have become an increasingly popular mode oftravel, notably as a response to our current society difficu lties, such as petrol cast. traffic jams, and the needs for mobi lity. As a result of this grawing use, the crashes PTW drivers are victims of in terms of morta lity and morbidity represent an actual problem of public health. PTW have come to the limelight of raad safety and their accidents question the traffic system as a who le. The problem is not as simple as it is sometimes considered, and in arder to defi ne efficient solutions, we need togo fu rtherthan an ove rail analysis. We have to know more about the different facets of the varia us difficulties th at PTW meet when interacting with the road layout and with the traffic.

An unfair risk

The motorized t wo-whêeled vehicles riders are, with the pedestrians and bicyclists, the users most exposed to the raad risk. Statistical data show that they represent 16% of people killed on the raad in Eu rope (SafetyNet. 2008) whereas they re present less than 2% of the quan-tity of mobility. An eloquent indicator oftheir weakness is the risk to be ki l led as regard to the mileage. The risk per km is thus 20 times superior on a motorized twowheeler vehicle th an in the car. And perhaps even worse is the risk of being severely injured, with hand icap for life (Amoros, Martin and Lau mon, 2008). Furthermore, it is known that accident reporting in national databases is incomplete and there are indications that it is more incomplete for motorcycle and moped riders th an for car occupants (Eivik and Va a, 2004).1t is notably the case for single vehicle accidents which are specifically underestimated for PTW. This excess risk co mes partly from the greater vu lnerability of the PTW users, in the sense that. with the absence of protection, the least collision exposes them to often serious wounds. But they also come from a stronger involvement in certain types of accidents. These two characteristics of their accidentai ness attest a certain inadequacy between the motorized two-wheeled vehicle and the current driving system. We must consider that. historically, this system have been essentially conceived and directed according to the problems of cars traffic flow. lt requires an effort of adaptation towards the motorized two-wheeled vehicles as being an integral part of raad users, to whom the traffic system should have the objective to be adapted .

Why is it so difficult to solve the problem? ln relation with their development. the motorized twowheelers' population constitutes an increasingly heterogeneous family, with regard to the types of vehicle (trail, sporting, scooter, etc), the very strang diversity of t heir characteristics, as weil as the diversification of their use (from the motor bike "for fun" up to the "utilitarian" motor bike). Such a disparity of the modes, uses, attit udes (in particular with respect to risk ta king) conditions particular practices which are not without consequence on the va rious problems of interaction met within the traffic, and on the accidents which results from it. The different facets of the motorized twowheelers problemat ic thus deserve to be apprehended in-depth from the point of view of the ir determinants and their consequences in terms of both primary and secondary safety. The various forms of accidents proceed from specifie mechanisms which are essential to highlight so asto cover the range of the problem s. One cannot speak about "the PTW" but "the PTWS". One cannot speak eit her about "the problem" of the motorized two-wheelers, but about the plurality of the problems which their inscription in the driving system underlies. The problems they represent being plura l, they must be studied operationa lly in the ir variou s facets. Only under the condition of a weil documented knowledge of t his plurality, adapted solutions could be defined in a targeted way.

What are the key questions for enhancing ptw safety on the road?

Crashes can be def ined as mu lti-factorial processes. Every single accident case involves a combination of causes, the resu lt of which being the incapacity of the road users to compensate for the difficult ies encountered. The se different types of factors act along the malfunction prod uction chain, from the "driving phase" to the "impact phase" (figure 1). Safety measures should, in the same way, be found at these different levels, whether by acting on the drivers (including "other" road users}, on the vehicles or/and on the road environ ment.

Lack of protection

Impact phase

Among the key questions that can be drawn from research works found in the literature, we can briefly mention the foilowings 1 :

• PTW conspicuity A large a mount of research works insist on the fact that PTW are more difficu lt to perceive than other vehicles, and that this poor "conspicuity" plays an im portant role in accident occurring. However, such a result is governed by complex mechanisms involving perceptive, cognitive and behavioral factors. A better knowledge of these underlying factors will condition the efficiency of the measures ta ken.

• PTW users, usage, culture and risk exposure Very few knowledge exist s on the precise risk exposure of PTW users. lt would thus be useful to put forward studies to know better the variety of PTW users and the variety of their mobility behavior, in order to identify weil targeted strategies of prevention. Led on the European scale, this work could ailow better documented comparisons of the accident risk on motorized twowheelers between count ries. Further upstream social and cultural questions should a Iso be investigated as far as they condition driving behavior at its early stages.

• Training and licensing

The effect of training is complex and has sometimes proved to be counterproductive, depending on the content and the aim of the instruction. As a genera l point, PTW training should be more oriented toward the development of prevention abilities than recuperation skil ls acquisition. Training should also concern other road users, with the aim to ailowing them to better interact with PTW. Besides, the introduction of a graduated driving licence for motorcyclists has been shown to be associated with a safety benefit.

• Technological systems PTW is a vehicle which presents particular difficulties of driving. So it asks for the development of specifie driving aids. The f irst works on the equipment of antilock brakes on motorcycles have been found to reduce overall accident involvement and severity. other systems are to be developed, useful in driving situation (e.g. early detection of the situat ions at risk), as it in emergency situation (e.g. braking and stabi lity improvement). Safety deviees allowing the other users to better detect and interact with the PTW a Iso are to be developed and evaluated.

• An infrastructure helpful, tolerant and protective for PTW users PTW is a vehicle particularly sensitive to the characteristics of infrastructure (curve radius. friction, visibility, possibility of recuperation. fixed obstacles. etc.). A difficulty easily compensated for on four wheels can become a major drawback on two wheels. Three aspects are to be considered in order to promote a safe road layout for PTW: 1/ A "helpful" infrastructure, allowi ng the rider not to fi nd himself in critical situation, 2/ A "tolerant" infrastructure, allowing this user to recover his own errors and those of the others. 3/ A "protective" infrastructure, t a king into account better the PTW riders vulnerability in case of impact. Works to increase the knowledge in these doma ins. still too fragmented, are to be developed.

• Protection deviees

Continuous progresses have to be done to reduce PTW riders' vulnerability. The appropriate safety deviees must take into account their practicability fo r their user: ergonomies, cost. adaptation to weather conditions (for exa mple su mmer t i me).

• Evaluation of safety nîeasures ln a general way. the safety measures suffer from of a Jack of objective evaluation of their efficiency. lt would be advisable to put forward studies estimati ng the effects of t he actions dedicated to PTW users.

International Activities, abstracts 13

Conclusion

Knowledge is progressing. but there is still a rea l need for research on the foundat ions underlying PTW insecurity, wit h a view to defining measures for add ressing its specificities and meeting the needs of each participant in the driving system. Beyond the observation of the inherent vulnerability of this form oftravel, it shou ld be considered th at PTWs have a specifie dynamic behaviou r that sometimes leads to greater difficu lties of control in the same conditions. Their particular place in traffic should also be taken into account, with sizes and performances that can lead to special difficulties in interaction wit h othe r users of the road spa ce.

ln brief, we still need to progress in understanding the different mechanisms at work in this safety problems. This knowledge can be considered a necessary condition for defining more targeted. and therefore better suited, actions.

Figure 1 .

 1 Figure1. Main phases w ithin an accident sequence (from[START_REF] Van Elslande | Human factors: Summary Report[END_REF]


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

Vangelis Th

Paschos
email: paschos@lamsade.dauphine.fr

What about future? Robustness under vertex-uncertainty in graph-problems

We study a robustness model for graph-problems under vertex-uncertainty. We assume that any vertex v i of the input-graph G(V, E) has only a probability p i to be present in the final graph to be optimized (i.e., the final instance for the problem tackled will be only a sub-graph of the initial graph). Under this model, the original "deterministic" problem gives rise to a new (deterministic) problem on the same input-graph G, having the same set of feasible solutions as the former one, but its objective function can be very different from the original one, the set of its optimal solutions too. Moreover, this objective function is a sum of 2 |V | terms; hence, its computation is not immediately polynomial. We give sufficient conditions for large classes of graph-problems under which objective functions of the robust counterparts are polynomially computable and optimal solutions are well-characterized. Finally, we apply these general results to natural and well-known representatives of any of the classes considered.

Introduction

Very often people has to make decisions under several degrees of uncertainty, i.e., when only probabilistic information about the future is available. We deal with the following robustness model under data uncertainty. Consider a generic instance I of a combinatorial optimization problem Π. Assume that Π is not to be necessarily solved on the whole I, but rather on a (unknown a priori) sub-instance I ′ ⊂ I. Suppose that any datum d i in the data-set describing I has a probability p i , indicating how d i is likely to be present in the final sub-instance I ′ . Consider finally that once I ′ is specified, the solver has no opportunity to solve it directly (for example she/he has to react quasi-immediately, so no sufficient time is given her/him). Concrete examples of such situations dealing with satellite shots planning or with timetabling are given in [START_REF] Murat | On the probabilistic minimum coloring and minimum kcoloring[END_REF][START_REF] Murat | Probabilistic combinatorial optimization on graphs[END_REF].

What can the solver do in this case? A natural way to proceed is to compute an anticipatory solution S for Π, i.e., a solution for the entire instance I, and once I ′ becomes known, to modify S in order to get a solution S ′ fitting I ′ . The objective is to determine an initial solution S for I such that, for any sub-instance I ′ ⊆ I presented for optimization, the solution S ′ respects some predefined quality criterion (for example, optimal for I ′ , or achieving, say, constant approximation ratio, or . .

. ).

In what follows we restrict ourselves in graph-problems and consider the following very simple and quick modification 1 of S: take the restriction of S in the present sub-instance of G. Consider a graph-problem Π, a graph G(V, E) of order n, instance of Π, and an n-vector Pr = (p 1 , . . . , p n ) of vertex-probabilities any of them, say p i , measuring how likely is for vertex v i ∈ V , i = 1, . . . , n to be present in the final subgraph G ′ ⊆ G, on which the problem will be really solved. For any solution S for Π in G and for any V ′ ⊆ V , denote by S ′ the restriction of S in V ′ , i.e., the set resulting from S after removal of the vertices that do not belong to V ′ . As we have mentioned, S ′ , can or cannot (depending of the definition of Π) be a feasible solution of Π in the subgraph G ′ of G induced by V ′ . Whenever S ′ is feasible, denote by m(G ′ , S ′ ) the objective value of S ′ in G ′ . Then, the value of S for G, denoted by E(G, S) (and frequently called functional ), is the expectation of m(G ′ , S ′ ), over all the possible G ′ ⊆ G. Formally, given S, the functional E(G, S) of S is defined by: E(G, S) =

V ′ ⊆V Pr V ′ m G ′ , S ′ (1)
where Pr[V ′ ] is the probability that V ′ will be finally the real instance to be optimized and is defined by:

Pr[V ′ ] = v i ∈V ′ p i v i ∈V \V ′ (1 -p i ).
Obviously, E(G, S) depends also on Pr but, for simplicity, this dependency will be omitted. Quantity, E(G, S) can be seen as the objective function of a new combinatorial problem, derived from Π and denoted by robust Π in what follows, where we are given an instance G of Π and a probability vector Pr on the vertices of G and the objective is to determine a solution S * in G optimizing E(G, S) (optimal anticipatory solution). The optimization goal of robust Π is the same as the one of Π. This way to tackle robustness in combinatorial optimization is sometimes called a priori optimization (this term has been introduced by [START_REF] Bertsimas | A priori optimization[END_REF]) and can also be seen as a particular case of stochastic optimization ( [START_REF] Birge | Introduction to stochastic programming[END_REF][START_REF] Prekopa | Stochastic programming[END_REF]). In a priori optimization, the combinatorial problem to be solved, being subject to hazards or to inaccuracies, is not defined on a static and clearly specified instance, since the instance to be effectively optimized is not known with absolute certainty from the beginning. Robustness requirements are due to the fact that uncertainty in the presence of data makes that it is not possible to assign unique values to some parameters of the problems. In such an approach, the goal is to compute solutions that behave "well" under any assignment of values to these parameters. Under this model, restrictive versions of routing and network-design robust minimization problems (in complete graphs) have been studied 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]. Recently, in [START_REF] Bianchi | Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms[END_REF], the analysis of the robust 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. In [START_REF] Murat | The probabilistic minimum vertex-covering problem[END_REF][START_REF] Murat | On the probabilistic minimum coloring and minimum kcoloring[END_REF] the minimum vertex covering and the minimum coloring are tackled, while in [START_REF] Murat | The probabilistic longest path problem[END_REF][START_REF] Murat | A priori optimization for the probabilistic maximum indepenset problem[END_REF] robust maximization problems, namely, the longest path and the maximum independent set, are studied. An early survey about a priori optimization can be found in [START_REF] Bellalouna | Probabilistic combinatorial problems: a new domain in operational research[END_REF] while, a more recent one appears in [START_REF] Murat | L'optimisation combinatoire probabiliste[END_REF].

Another way to apprehend robustness under uncertainty is as it is done in [START_REF] Averbakh | On the complexity of a class of combinatorial optimization problems with uncertainty[END_REF][START_REF] Deȋneko | On the robust assignment problem under a fixed number of cost scenarios[END_REF][START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF][START_REF] Montemanni | A branch and bound algorithm for the robust shortest path problem with interval data[END_REF][START_REF] Mulvey | Robust optimization of large-scale systems[END_REF]. In this framework, one either identifies different feasible scenarii, or associates an interval of values rather than one unique value with a parameter. Finally, a third very interesting face of robustness that model inaccuracy by assigning probabilities to scenarii or to data is apprehended by what has been called two-and multi-stage stochastic optimization (see, for example, [START_REF] Gupta | Boosted sampling: approximation algorithms for stochastic optimization[END_REF][START_REF] Gupta | What about wednesday? approximation algorithms for multistage stochastic optimization[END_REF][START_REF] Ravi | Hedging uncertainty: approximation algorithms for stochastic optimization problems[END_REF] for recent results on this area).

Our goal is to go beyond study of robust versions of particular combinatorial problems and to propose a structural study of robustness under uncertainty for the a priori optimization paradigm. Here, the main mathematical issues (assuming that, given an anticipatory solution S, its restriction to G[V ′ ] is feasible) are:

• the complexity of the computation of E(G, S) which, carrying over 2 n additive terms, is non-trivially polynomial;

• compact combinatorial characterization (based upon the form of E(G, S)) of S * as optimal solution of robust Π;

• the complexity of computing S * , at least for particular classes of subproblems of the initial problem.

Notice that, for any problem Π, its combinatorial counterpart robust Π contains Π as subproblem (just consider probability vector (1, . . . , 1) for Π). Hence, from a complexity point of view, robust Π is at least as hard as Π, that is, if Π is NP-hard, then robust Π is also NP-hard, while if Π is polynomial, then no immediate indication can be provided for the complexity of robust Π, until this latter problem is explicitly studied.

In what follows, in Sections 2, 3 and 4, we deal with three categories of combinatorial graphproblems exhausting a very large part of the most known ones, namely:

• problems whose solutions are subsets of the input vertex-set verifying some specific property (Section 2);

• problems whose solutions are collections of subsets of the input vertex-set verifying some specified non-trivial hereditary property2 (Section 3);

• problems whose solutions are subsets of the input edge-set verifying some specific property (Section 4).

For any of these categories, we give sufficient conditions under which functionals are analytically expressible and polynomially computable and anticipatory solutions are well-characterized.

In Section 5, we deal with problems having as solutions subsets of the input edge-set verifying some connectivity properties. For this type of problems, the restriction of S to G[V ′ ] is not feasible in general, but some additional work (with low algorithmic complexity) is sufficient in order to render this set feasible. There, as we will see, anticipatory solutions cannot be as wellcharacterized as previously, neither complexity of computing S * . However, we give sufficient conditions under which functionals for the robust counterparts of these problems are computable in polynomial time.

These structural results immediately apply to several well-known problems, for instance, min vertex cover, max independent set, min coloring, max cut, max matching, etc., producing so particular results interesting per se. Furthermore, the scope of our results is even larger than for graph-problems, as problems not originally defined on graphs (e.g., max set packing or min set cover), are also captured. So, this work can provide a framework for a systematic classification of a great number of robust derivatives of well-known graph-problems.

In what follows, we deal with problems in NPO. Informally, this class contains optimization problems whose decision versions belong to NP. Given a combinatorial problem Π ∈ NPO, we denote by robust Π, its robust counterpart defined as described previously and assume that the vertex-probabilities are independent.

Let A be a polynomial time approximation algorithm for an NP-hard graph-problem Π, let m(G, S) be the value of the solution S provided by A on an instance G of Π, and opt(G) be the value of the optimal solution for G (following our notation for robust Π, opt(G) = E(G, S * )). The approximation ratio ρ A (G) of the algorithm A on G is defined by ρ A (G) = m(G, S)/opt(G). An approximation algorithm achieving ratio, at most, ρ on any instance G of Π will be called ρ-approximation algorithm.

Solutions are subsets of the initial vertex-set

In this section, we deal with graph-problems whose solutions are subsets of the vertex-set of the input-graph and where, given such a solution S and a set V ′ ⊆ V , the restriction of S in V ′ , i.e., the set

S ′ = S ∩ V ′ is feasible for G[V ′ ].
The main result of this section is stated in Theorem 1.

Theorem 1. Consider a graph-problem Π verifying the following assumptions: (i) an instance of Π is a vertex-weighted graph G(V, E, w); (ii) solutions of Π are subsets of V ; (iii) for any solution S and any subset

V ′ ⊆ V , S ′ = S ∩ V ′ is feasible for G ′ = G[V ′ ];
(iv) the value of any solution S ⊆ V is defined by: m(G, S) = w(S) = v i ∈S w i , where w i is the weight of v i ∈ V . Then, the functional of robust Π is expressed as: E(G, S) = v i ∈S w i p i and can be computed in polynomial time. Furthermore, the complexity of robust Π is the same as the one of Π.

Proof. Fix a subset V ′ ⊆ V and an anticipatory solution S for robust Π on G. According to assumption (iii), S ′ is feasible for G[V ′ ]. Its value is given by: m(G ′ , S ′ ) = v i ∈S w i 1 {v i ∈V ′ } . Then, denoting by 1 F the indicator function of a fact F and using (1) we get:

E(G, S) = V ′ ⊆V m G ′ , S ′ Pr V ′ = V ′ ⊆V v i ∈S w i 1 {v i ∈V ′ } Pr V ′ = v i ∈S w i V ′ ⊆V 1 {v i ∈V ′ } Pr V ′ (2)
For any vertex

v i ∈ V , let V i = V \ {v i } and V ′ i = {V ′ ⊆ V : V ′ = {v i } ∪ V ′′ , V ′′ ⊆ V i }.
Using also the fact that presence-probabilities of the vertices of V are independent, we get:

V ′ ⊆V 1 {v i ∈V ′ } Pr V ′ = V ′ ∈V ′ i Pr V ′ = V ′′ ⊆V i Pr {v i } ∪ V ′′ = V ′′ ⊆V i Pr [v i ] Pr V ′′ = Pr [v i ] V ′′ ⊆V i Pr V ′′ = p i (3)
Combination of (2) and (3) immediately leads to the expression claimed for E(G, S).

It is easy to see that this functional can be computed in time linear in n. Furthermore, computation of the optimal anticipatory solution for robust Π in G, obviously amounts to the computation of the optimal weighted solution for Π in G(V, E, w ′ ), where, for any v i ∈ V , w ′ i = w i p i . Consequently, by this observation and by assumption (iv) in the statement of the theorem, Π and robust Π have the same complexity.

Although computation of the functional is, as we have mentioned, a priori exponential (since it carries over 2 n subgraphs of G), assumptions (i) through (iv) in Theorem 1 allow polynomial computation of its value. This is due to the fact that, under these assumptions, given a subgraph G ′ induced by a subset V ′ ⊆ V , the value of the solution for G ′ is the sum of the weights of the vertices in S ∩ V ′ . Furthermore, a vertex not in S will never make part of any solution in any sub-graph of G. Consequently, computation of the functional amounts to determining, for any G ′ , which vertices make part of S ∩ V ′ . This is equivalent with the specification, for any v i ∈ S, of all the subgraphs to which v i belongs and with a summation of the presence-probabilities of these subgraphs. This sum is equal to p i (the probability of v i ). This simplification is the main reason that renders functional's computation polynomial, despite of the exponential number of terms in its generic expression.

Notice that Theorem 1 can also be used for getting generic approximation results for robust Π. Indeed, since this problem is a particular weighted version of Π, one immediately concludes that if Π is approximable within approximation ratio ρ, so is robust Π.

Corollary 1. Under the hypotheses of Theorem 1, whenever Π and robust Π are NP-hard, they are equi-approximable.

Theorem 1 has also the following immediate corollary dealing with the case of robust versions of unweighted combinatorial optimization problems.

Corollary 2. Consider a robust combinatorial optimization problem robust Π verifying assumptions (i) to (iv) of Theorem 1 with w = 1. Then, the functional of robust Π, is expressed as: E(G, S) = v i ∈S p i and can be computed in polynomial time. Furthermore, robust Π is equivalent to a weighted version of Π where vertex-weights are the vertex-probabilities.

Corollary 2 is somewhat weaker than Theorem 1 since it does not establish the equivalence between Π and robust Π but rather a kind of reduction from Π to robust Π stating that the latter is a priori harder than the former one. As a consequence, whenever Π is NP-hard, so is robust Π whereas if Π is polynomial, the status of robust Π remains unclear by Corollary 2.

Applications of Theorem 1

Theorem 1 can be applied to a broad class of problems that fit its four conditions, as robust max independent set ( [START_REF] Murat | A priori optimization for the probabilistic maximum indepenset problem[END_REF]), robust min vertex covering ( [START_REF] Murat | The probabilistic minimum vertex-covering problem[END_REF]), etc. We describe in what follows two further applications, namely, robust max induced subgraph with property π and robust min feedback vertex-set.

robust max induced subgraph with property π

Consider a graph G(V, E) and a non-trivial hereditary property. A feasible solution for max induced subgraph with property π is a subset

V ′ ⊆ V such that, the subgraph G[V ′ ] of G induced by V ′ satisfies π.
The objective for max induced subgraph with property π is to determine such a set V ′ of maximum-size. Note that, "independent set", "clique", "planar graph" are hereditary properties. In the weighted version of the problem (i.e., the one where positive weights are associated with the vertices of G), called max weighted induced subgraph with property π, we search for maximizing the total weight of V ′ .

Given a solution S for max weighted induced subgraph with property π and an induced subgraph

G[V ′ ] of the input graph G(V, E), the set S ∩V ′ is a feasible solution for G[V ′ ],
since, by the definition of π, if a subset S ⊆ V induces a subgraph verifying it, then any subset of S also induces a subgraph verifying π. Henceforth, max weighted induced subgraph with property π fits the conditions of Theorem 1, or of Corollary 2 (for the unweighted case).

robust min feedback vertex-set

Given an oriented graph G(V, A), a feedback vertex-set is a subset V ′ ⊆ V such that V ′ contains at least a vertex of any directed cycle of G. In min feedback vertex-set, the objective is to determine a feedback vertex-set of minimum size.

Remark that, absence of a vertex v from a feedback vertex-set V ′ , breaks any cycle containing this vertex. If v makes part of an anticipatory solution S then, since no such cycle that contained v exists in G ′ , feasibility of the solution S ∩V ′ does not suffer from the absence of v. So, Corollary 2 applies for this problem.

Note that the weighted version of this problem can be tackled in a similar way.

Extensions of Theorem 1 beyond graphs

Theorem 1 can also be used to capture problems that are not originally defined on graphs as robust max set packing and robust min set cover. The robust versions dealt for both of them consist of considering presence probabilities p 1 , . . . , p n for the corresponding elements of the ground set C. Extensions to these problems are shown in the following Sections 2.2.1 and 2.2.2.

robust max set packing

Given a family S = {S 1 , . . . , S m } of subsets of a ground set C = {c 1 , . . . , c n }, max set packing consists of determining a maximum size sub-collection S ′ ⊆ S such that for any

(S i , S j ) ∈ S ′ ×S ′ , S i ∩ S j = ∅.
The robust version assumed for max set packing consists of considering presence probabilities p 1 , . . . , p n for the corresponding elements of C. A set S i ∈ S is present if at least one of its elements is present. So, denoting by Pr[S i ] the presence probability of the set S i = {c i 1 , c i 2 , . . . , c i k }, we get:

Pr [S i ] = 1 - k j=1 1 -p i j (4)
Consider the following very well-known transformation of an instance (S, C) of max set packing into an instance G(V, E) of max independent set:

• for any S i ∈ S, add a new vertex v i ∈ V ;

• for any pair (S i , S j ) ∈ S × S, if S i ∩ S j = ∅, then add an edge

(v i , v j ) ∈ E.
It is easy to see that, under the above transformation, any set packing in (S, C) becomes an independent set of G of the same size and vice-versa. So, given a robust model for max set packing, one can transform, as described just previously, its instance (S, C) into a graph G(V, E) and one can consider vertex probabilities p(v i ) = Pr[S i ], i = 1, . . . , m, where v i is the vertex added for S i . A feasible max independent set-solution S ′ in G corresponds to a sub-family S ′ consisting of the sets represented by the vertices of S ′ and is indeed a set packing. On the other hand, an induced subgraph G[V ′ ] of G corresponds to a sub-instance I ′ of (S, C) induced by the sets represented by the vertices of V ′ (according to the rule that a set is present if at least one of its elements is in I ′ ). Then, taking the restriction of S ′ in V ′ amounts to consider the restriction of S ′ in I ′ . It is easy to see that this restriction is a feasible set packing for I ′ . So, max set packing, being an independent set problem, meets conditions of Corollary 2 (or of Theorem 1 for max weighted set packing). Hence, given an instance (S, C) of max set packing, with element-probabilities p i , for any c i ∈ C, and a feasible solution S ′ of (S, C), then E((S, C), S ′ ) = S i ∈S ′ Pr[S i ], where Pr[S i ] is as defined in [START_REF] Bertsimas | Probabilistic combinatorial optimization problems[END_REF]. Then, the robust version of max set packing amounts to a particular weighted version of max set packing where each set

S i = {c i 1 , . . . , c i k } in S is weighted by Pr[S i ].

robust min set cover: when sets become vertices

Given a collection S = {S 1 , . . . S m } of subsets of a ground set C = {c 1 , . . . , c n } (it is assumed that ∪ S i ∈S S i = C), min set covering consists of determining a minimum-size set cover of C, i.e., a minimum-size sub-collection S ′ of S such that ∪ S i ∈S ′ S i = C.
We use the same robust model for min set cover, i.e., we consider presence probabilities p 1 , . . . , p n for the corresponding elements of the ground set C. As previously in Section 2.2.1, a set S i ∈ S is present if at least one of its elements is present. So, Pr[S i ] is given by (4). We give a formulation of min set cover as a graph-problem and according this formulation, we show that robust min set cover fits conditions of Theorem 1.

Consider an instance (S, C) of min set cover and construct G S (V S , E S , ℓ), an edge-labelled multi-graph, as follows:

• for any set S i ∈ S, add a vertex v i ∈ V S ;

• for any pair S i , S j of sets in S, add a new edge

(v i , v j ) labelled by c k only if c k ∈ S i ∩ S j .
Under this formulation, min set cover amounts to determine the smallest subset of vertices covering all the labels in G S . Then, an analysis very similar to the one for robust max set packing in Section 2.2.1, concludes that, under the considered formulation, min set cover meets conditions of Theorem 1 (for the weighted case) or of Corollary 2 (for the unweighted one).

Solutions are collections of subsets of the initial vertex-set

We now deal with problems the feasible solutions of which are collections of subsets of the initial vertex-set. Consider a graph G(V, E) and a combinatorial optimization graph-problem Π whose solutions are collections of subsets of V verifying some specified non-trivial hereditary property (e.g., independent set, clique, etc.). The following theorem characterizes functionals and optimal anticipatory solutions for such problems.

Theorem 2. Consider a graph-problem Π verifying the following assumptions: (i) an instance of Π is a graph G(V, E); (ii) a solution of Π on an instance G is a collection S = (V 1 , . . . , V k ) of subsets of V any of them satisfying some specified non-trivial hereditary property; (iii) for any solution S and any subset

V ′ ⊆ V , the restriction S ′ of S in V ′ , i.e., S ′ = (V 1 ∩ V ′ , . . . , V k ∩ V ′ ), is feasible for G ′ = G[V ′ ]; (iv) the value of any solution S ⊆ V of Π is defined by: m(G, S) = |S| = k. Then, E(G, S) = k j=1 (1 -v i ∈V j (1 -p i ))
and can be computed in polynomial time. robust Π amounts to a particular weighted version of Π, where the weight of any vertex

v i ∈ V is 1 -p i , the weight w(V j ) of a subset V j ⊆ V is defined by w(V j ) = 1 -v i ∈V j (1 -p i )
and the objective function to be optimized is equal to V j ∈C w(V j ).

Proof. Consider an anticipatory solution

S = (V 1 , V 2 , . . . , V k ) and a subgraph G ′ = G[V ′ ] of G. Denote by k ′ = m(G ′ , S ′
), the value of the solution obtained on G ′ as described in assumption (iii). Then, from (1), E(G, S)

= V ′ ⊆V Pr[V ′ ]k ′ .
Consider the facts F j : V j ∩ V ′ = ∅ and Fj : V j ∩ V ′ = ∅. Then, k ′ can be written as

k ′ = k j=1 1 F j = k j=1 (1 -1 Fj
) and E(G, S) becomes:

E(G, S) = V ′ ⊆V Pr V ′   k j=1 1 -1 Fj   = V ′ ⊆V Pr V ′ k j=1 1 - V ′ ⊆V Pr V ′ k j=1 1 V j ∩V ′ =∅ = k j=1 V ′ ⊆V Pr V ′ - k j=1 V ′ ⊆V Pr V ′ 1 V j ∩V ′ =∅ = k - k j=1 v i ∈V j (1 -p i ) = k j=1   1 - v i ∈V j (1 -p i )   (5)
It is easy to see that computation of E(G, S) can be performed in at most O(n) steps; consequently, robust Π is in NPO. Furthermore, by [START_REF] Bertsimas | On probabilistic traveling salesman facility location problems[END_REF], the characterization of the feasible solutions for robust Π claimed in the statement of the theorem is immediate.

What does play a central role for yielding result of Theorem 2, is the fact that property satisfied by the sets of the collection is hereditary. This allows to preserve sets V 1 , . . . , V k in the solution returned by S ∩ V i , i = 1, . . . , k, unless they are empty and, consequently, to express E(G, S) as in [START_REF] Bertsimas | On probabilistic traveling salesman facility location problems[END_REF], in terms of facts F j and Fj .

Assume that p i = 1, for any v i ∈ V . Then, by ( 5), E(G, S) = k and robust Π coincides in this case with Π.

Corollary 3. If Π is NP-hard, then robust Π is also NP-hard.
As for Corollary 2, Corollary 3 settles complexity only for the case where Π is NP-hard, leaving unclear the status of robust Π when Π ∈ P.

Applications of Theorem 2

Theorem 2 has also application for numerous combinatorial optimization problems, as robust min coloring ( [START_REF] Murat | On the probabilistic minimum coloring and minimum kcoloring[END_REF]), robust min partition into cliques, etc. In what follows we describe two further applications, namely, to robust min complete bipartite subgraph cover and robust min cut cover.

robust min complete bipartite subgraph cover

Given a graph G(V, E), a solution of min complete bipartite subgraph cover is a collection C = (V 1 , V 2 , . . . , V k ) of subsets of V such that the subgraph induced by any of the V i 's, i = 1, . . . , k, is a complete bipartite graph and for any edge (u, v) ∈ E there exists a V i containing both u and v. The objective here is to minimize the size |C| of C.

Consider a solution S = (V 1 , . . . , V k ) min complete bipartite subgraph cover and a subset

V ′ ⊆ V . The set S ′ = (V 1 ∩ V ′ , . . . , V k ∩ V ′ ), is feasible for G ′ = G[V ′ ].
Indeed, if a vertex v disappears from some subset V i of an anticipatory solution S, the surviving set V i always induces a complete bipartite graph. Furthermore:

• except the edges that have been disappeared (the ones incident to v) any other edge remain covered by the surviving sets of S;

• property "is a complete bipartite graph" is hereditary.

So, robust min complete bipartite subgraph cover meets the conditions of Theorem 2.

robust min cut cover

Given a graph G(V, E), a feasible solution for min cut cover is a collection

(V 1 , . . . , V k ) of V such that any V i , i = 1, . . . , k is a cut, i.e., for any (u, v) ∈ E, there exists a V i such that either u ∈ V i and v / ∈ V i , or u / ∈ V i and v ∈ V i .
The objective is to minimize the size of the collection. Consider a solution S = (V 1 , . . . , V k ) for min cut cover. If a vertex v ∈ V is absent, then any edge incident to v is also absent. But, absence of a vertex together with any edge incident to it, does not affect the edges present to the final graph G ′ (V ′ , E ′ ), that remain feasibly covered by endpoints any of them belonging to distinct cuts. Hence, S ′ = (V 1 ∩V ′ , . . . , V k ∩V ′ ) is feasible for min cut cover, that meets the conditions of Theorem 2, since property "is a cut" is hereditary.

robust min set cover: when elements become vertices

As in Section 2, application of Theorem 2 can go beyond graphs. We give in this section another formulation of min set cover as a graph-problem that can be seen as a kind of dual with respect to the formulation given in Section 2.2.2. We show that, according this new formulation, robust min set cover fits conditions of Theorem 2. As we will see, both ways to tackle robust min set cover lead to the same result.

Consider an instance (S, C) of min set cover and this time construct an edge-colored multi-graph G C (V C , E C , ℓ S ) as follows:

• for any c i ∈ C, add a vertex v i ∈ V C ;

• for any pair c i , c j of elements in C, add a new edge (v i , v j ) colored with S k only if S k ⊇ {c i , c j }.

In the so-constructed graph G C a set S i = {c i 1 , . . . c i k } ∈ S becomes a clique on vertices v i 1 , . . . , v i k ∈ V C all the edges of which are colored with the same color S i ; we will call such a clique a unicolored clique. Under this alternative formulation, min set cover can be viewed as a particular clique-covering problem where the objective is to determine a minimum size covering of V C by unicolored cliques. Consider a set cover S ′ for the initial instance (S, C) a sub-instance I ′ of (S, C) consisting of some elements of C and of the subsets of S including these elements. These objects correspond, in G C , to a vertex-covering by unicolored cliques and the subgraph G ′ C of G C defined with respect to I ′ . Restriction of S ′ in I ′ , can be viewed, with respect to G C as restriction of the initial vertexcovering by unicolored cliques to the vertices of G ′ C just as described in Section 3. Observe finally that "unicolored clique" is a hereditary property. So, under this formulation, robust min set cover exactly fits conditions of Theorem 2.

So, according to any of the formulations used for min set cover, given an instance (S, C) of min set cover, with element-probabilities p i , for any c i ∈ C, and a feasible solution S ′ of (S, C), then, E((S, C), S ′ ) = S i ∈S ′ (1c j ∈S i (1p j )) and can be computed in polynomial time. The robust version of min set cover amounts to a particular weighted version of the initial problem where each set S = {c i 1 , . . . , c i k } in S is weighted as in (4).

Hence, robust min set cover is indeed a simple weighted version of min set cover, where one has to determine a set cover minimizing its total weight. In this sense, the problem dealt seems to be simpler than the majority of the problems captured by Theorem 2 as, for instance min coloring. This is due to the fact that, dealing with min set cover, there is a polynomial number of unicolored cliques in G C (the sets of S) candidate to be part of any solution, while, for min coloring the number of the independent sets that may be part of a solution is exponential.

A generic approximation result for the problems fitting conditions of Theorem 2

This section extends an approximation result of [START_REF] Murat | On the probabilistic minimum coloring and minimum kcoloring[END_REF] for robust min coloring, in order to capture the whole of problems meeting the conditions of Theorem 2.

Consider such an NPO problem Π, an instance G(V, E) of Π, set n = |V | and consider a solution S = (V 1 , . . . , V k ) of Π on G. Denote by p min and p max the minimum and maximum vertex-probabilities, respectively. Then, the following bounds hold for E(G, S):

max    n i=1 p i - n i=1 n j=i+1 p i p j , kp min    E(G, S) min n i=1 p i np max , k (6)
Observe first that the rightmost upper bound for E(G, S) in ( 6) is immediately derived from the expression for E(G, S) in the statement of Theorem 2.

We now prove the leftmost upper bound and lower bound of [START_REF] Bertsimas | The probabilistic minimum spanning tree problem[END_REF]. We first produce a framing for the term 1v i ∈V j (1p i ). For simplicity, assume |V j | = ℓ and arbitrarily denote vertices in V j by v 1 , . . . , v ℓ . Then, by induction in ℓ the following holds:

ℓ i=1 p i - ℓ i=1 ℓ j=i+1 p i p j 1 - ℓ i=1 (1 -p i ) ℓ i=1 p i (7)
Indeed, for the left-hand side of [START_REF] Bertsimas | A priori optimization[END_REF], observe first that it is true for ℓ = 1 and suppose it true for ℓ = κ, i.e., κ i=1 p i -κ i=1 κ j=i+1 p i p j 1 -κ i=1 (1p i ), or:

κ i=1 (1 -p i ) 1 - κ i=1 p i + κ i=1 κ j=i+1 p i p j (8)
Suppose now that ℓ = κ + 1 and multiply both terms of ( 8) by (1p κ+1 ); then:

κ+1 i=1 (1 -p i )   1 - κ i=1 p i + κ i=1 κ j=i+1 p i p j   (1 -p κ+1 ) = 1 - κ i=1 p i + κ i=1 κ j=i+1 p i p j -p κ+1 + p κ+1 κ i=1 p i -p κ+1 κ i=1 κ j=i+1 p i j = 1 - κ+1 i=1 p i + κ+1 i=1 κ+1 j=i+1 p i p j -p κ+1 κ i=1 κ j=i+1 p i p j 1 - κ+1 i=1 p i + κ+1 i=1 κ+1 j=i+1 p i p j
which proves the left-hand side inequality in [START_REF] Bertsimas | A priori optimization[END_REF].

For the right-hand side of ( 7), we show by induction on ℓ that ℓ i=1 (1p i ) 1 -ℓ i=1 p i . This is clearly true for ℓ = 1. Suppose it also true for any ℓ κ, i.e., κ i=1 (1p i ) 1 -κ i=1 p i . Then, by multiplying both members of this inequality by (1p κ+1 ), we get that the product obtained is equal to 1p κ+1 -κ i=1 p i + p κ+1 κ i=1 p i 1 -κ+1 i=1 p i , q.e.d. Taking the sums of the members of ( 7) for m = 1 to k, the right-hand side inequality immediately gives E(G, S) n i=1 p i . We now prove that E(G, S) n i=1 p i -n i=1 n j=i+1 p i p j , i.e., the leftmost lower bound claimed in [START_REF] Bertsimas | The probabilistic minimum spanning tree problem[END_REF]. From the left-hand side of (7), we get:

k m=1   ℓ i=1 p i - ℓ i=1 ℓ j=i+1 p i p j   = n i=1 p i - k m=1 ℓ i=1 ℓ j=i+1 p i p j n i=1 p i - n i=1 n j=i+1 p i p j (9)
Observe that, from the first inequality of (7), we have:

k m=1   ℓ i=1 p i - ℓ i=1 ℓ j=i+1 p i p j   k m=1 1 - ℓ i=1 (1 -p i ) (10)
The righthand side of [START_REF] Deȋneko | On the robust assignment problem under a fixed number of cost scenarios[END_REF] is exactly E(G, S). Putting this together with (9), the leftmost lower bound for E(G, S) in ( 6) is proved. Finally, in order to derive the rightmost lower bound in [START_REF] Bertsimas | The probabilistic minimum spanning tree problem[END_REF], observe that

v i ∈S j (1 -p i ) (1 -p min ) |S j | 1 -p min , i.e., 1 -v i ∈S j (1 -p i ) p min .
Summing for j = 1 to k, we get the bound claimed.

We are ready now to study an approximation algorithm for the whole class of problems meeting Theorem 2. Fix a vertex-probability p ′ , assume that there exists a ρ-approximation polynomial time algorithm A for Π, and run the following algorithm, called RA for robust Π:

1. partition the vertices of G into three subsets: the first, V 1 including the vertices with probabilities at most 1/n, the second, V 2 , including the vertices with probabilities in the interval [1/n, p ′ ] and the third, V 3 , including the vertices with probabilities greater than p ′ ;

2. feasibly solve Π in G[V 1 ] and G[V 2 ] separately; 3. run A in G[V 3 ];
4. take the union of the solutions computed in steps 2 and 3 as solution for G. Proof. Denote by S * = (V * 1 , . . . , V * k * ) an optimal anticipatory solution and by S = ( V1 , . . . , Vk ) the approximate solution computed in step 4 and, respectively by

S * i = (V * 1,i , . . . , V * |S * i |,i
) and S i = ( V1,i , . . . , V|S i |,i ), the optimal and approximate solutions in

G[V i ], i = 1, 2, 3. Denote by S * [V 1 ], S * [V 2 ] and S * [V 3 ] the restrictions of S * in G[V 1 ], G[V 2 ] and G[V 3 ]
, respectively. Denote finally by n i , the orders of G[V i ], for i = 1, 2, 3, respectively. The proof is based upon the following claims:

1. any feasible polynomial time approximation algorithm for robust Π achieves in

G[V 1 ]
approximation ratio bounded above by 2;

2. any feasible polynomial time approximation algorithm for robust Π achieves in G[V 2 ] approximation ratio bounded above by O(np ′ );

3. assuming that A achieves approximation ratio ρ for Π, algorithm RA, when running in

G[V 3 ],
achieves approximation ratio bounded above by ρ/p ′ for robust Π.

For Claim 1, using (6) for S 1 and S * 1 , we get:

E(G[V 1 ], S 1 ) n 1 i=1 p i and E(G[V 1 ], S * 1 ) n 1 i=1 p i -n 1 i=1 n 1 j=i+1 p i p j .
Combining them, we derive:

E (G [V 1 ] , S * 1 ) E (G [V 1 ] , S 1 ) 1 - n 1 i=1 n 1 j=i+1 p i p j n 1 i=1 p i = 1 - n 1 i=1 p i 2 - n 1 i=1 p 2 i 2 n 1 i=1 p i 1 - n 1 i=1 p i 2 + n 1 i=1 p 2 i 2 n 1 i=1 p i 1 - n 1 i=1 p i 2 (11)
Since p i 's are smaller than 1/n and n 1 n, the right-hand side of ( 11) is at least as large as 1/2. Hence, the approximation ratio of any algorithm for Π in G[V 1 ] is at most 2, and the proof of Claim 1 is complete.

We deal now with Claim 2. Here, for any v i ,

p i > 1/n. Consequently, 1 -v i ∈V * j,2 (1 -p i ) 1 -(1 -(1/n)) |V * j,2 | (|V * j,2 |/n) -(|V * j,2 |(|V * j,2 | -1)/2n 2 )
where the last inequality is an easy application of the left-hand side of [START_REF] Bertsimas | A priori optimization[END_REF] with p i = 1/n for any vertex v i . Furthermore:

V * j,2 n - V * j,2 V * j,2 -1 2n 2 = V * j,2 n   1 - V * j,2 -1 2n   V * j,2 n n + 1 2n V * j,2 2n (12)
all the subsets of V containing both v i and v j . Using also the fact that presence-probabilities of the vertices of V are independent, we get:

V ′ ⊆V 1 {(v i ,v j )∈E ′ } Pr V ′ = V ′ ∈V ′ ij Pr V ′ = V ′′ ⊆V ij Pr {v i } ∪ {v j } ∪ V ′′ = V ′′ ⊆V ij p i p j Pr V ′′ = p i p j V ′′ ⊆V ij Pr V ′′ = p i p j (14)
Combination of ( 13) and ( 14) immediately to the expression claimed for the functional.

It is easy to see that this functional can be computed in time quadratic with n. Furthermore, computation of an optimal anticipatory solution for robust Π in G obviously amounts to a computation of an optimal solution for Π in an edge-(or arc-) valued graph G(V, E, ℓ ′ ) where, for any

(v i , v j ) ∈ E, ℓ ′ (v i , v j ) = ℓ(v i , v j )p i p j .
Consequently, by this observation and by assumption (4), Π and robust Π have the same complexity.

The reasons for which the functional derived in Theorem 4 becomes polynomial are quite analogous to the ones in Theorem 1. Since an edge that does not belong to the anticipatory solution S will never be part of any solution in any subgraph G ′ (V ′ , E ′ ) of G, the computation of the functional amounts to the specification, for any G ′ , of the set S ∩ E ′ . This is equivalent to first determining, for any edge e ∈ S, all the subgraphs containing e and next to a summation of the probabilities of these subgraphs.This sum equals to the product of the probabilities of the endpoints of e.

Let us note that, as in Section 2, Theorem 4 can be used for getting generic approximation results for robust Π. Since this problem is a particular weighted version of Π, one immediately concludes that if Π is approximable within approximation ratio ρ, so is robust Π. Corollary 4. Under the hypotheses of Theorem 4, whenever Π and robust Π are NP-hard, they are equi-approximable.

Corollary 5. Consider a robust combinatorial optimization problem Π verifying assumptions (1) through (4) of Theorem 4 with ℓ = 1. Then, the functional of robust Π is expressed as: E(G, S) = (v i ,v j )∈S p i p j can be computed in polynomial time and robust Π is equivalent to an edge-(or arc-) valued version of Π where the values of an edge is the product of the probabilities of its endpoints.

Application of Theorem 4 to robust max matching

In max matching, the objective is, given a graph G(V, E) to determine a maximum-size matching, i.e., a maximum-size subset of E such that its edges are pairwise disjoint, in the sense that they have no common endpoint.

Clearly, max matching in both edge-valued and non-valued graphs, fits conditions of Theorem 4 and Corollary 5, respectively. Moreover, since max weighted matching is polynomial, both robust max weighted matching and robust max matching are polynomial also.

Application of Theorem 4 to robust max cut

We deal here with max cut in both edge-valued and unitary edge-valued graphs. Consider a graph G(V, E). In max cut (resp. max weighted cut) we wish to determine a maximum cardinality (resp., maximum weight) cut, that is to partition V into two subsets V 1 and V 2 such that a maximum number of edges (resp., maximum-weight set of edges) have one of their endpoints in V 1 and the other one in V 2 . We can represent an anticipatory cut S as a set of edges in such a way that whenever

(v i , v j ) ∈ S, v i ∈ V 1 and v j ∈ V 2 .
For example, in Figure 1(a), where for simplicity values of edges are not mentioned, the cut partitions V in subsets V 1 = {1, 3, 4, 7, 10, 13} and V 2 = {2, 5, 6, 8, 9, 11, 12} and the anticipatory cut S (thick edges) can then be written as S = {(1, 2), [START_REF] Bellalouna | Probabilistic combinatorial problems: a new domain in operational research[END_REF][START_REF] Bertsimas | The probabilistic minimum spanning tree problem[END_REF], (4, 2), [START_REF] Bertsimas | Probabilistic combinatorial optimization problems[END_REF][START_REF] Bertsimas | On probabilistic traveling salesman facility location problems[END_REF], [START_REF] Bertsimas | Probabilistic combinatorial optimization problems[END_REF][START_REF] Bertsimas | The probabilistic minimum spanning tree problem[END_REF], . . . , [START_REF] Jaillet | Probabilistic traveling salesman problem[END_REF][START_REF] Gupta | Boosted sampling: approximation algorithms for stochastic optimization[END_REF]} (where edges are ranged in lexicographic order). In Figure 1(b), we present graph's and cut's states assuming that vertices 4, 6 and 11 are absent. The solution S ′ considered misses in all edges of S having at least one endpoint among {4, 6, 11} but it obviously remains a feasible cut for the surviving graph.

Hence, both weighted and cardinality robust max cut meet the conditions of Theorem 4 Corollary 5, respectively. Consequently, max cut being NP-hard, robust max weighted cut and robust max cut are also NP-hard.

When things become complicated

In this section we tackle edge-weighted graph-problems where feasible solutions are connected sets of edges (for example, paths, trees, cycles, etc.) but we assume that, given a solution S and a set

V ′ ⊆ V inducing a subgraph G[V ′ ] = G ′ (V ′ , E ′ ) of G, the set S ∩ E ′ is not always feasible for G ′ .
Formally, consider a problem Π where a feasible solution is a connected set S of edges. Consider also that vertices in S are ordered in some appropriate order. Assume that operation S ∩ E ′ results in a set of connected subsets C 1 , C 2 , . . . , C k of S but that S ′′ = ∪ k i=1 C i is not connected (i.e., S ′′ does not constitute a feasible solution for Π). Assume also that connected subsets C 1 , C 2 , . . . , C k are also ranged in this order (always following some appropriate ordering implied by the one of S).

We consider a kind of "completion" of S ′′ by additional edges linking, for i = 1, . . . , k -1, the last vertex (in the ordering considered for S) of C i with the first vertex of C i+1 . In other words, given S (representing a connected set of edges), we apply the following algorithm, denoted by A in the sequel:

1. range the vertices of S following some appropriate order; 2. compute S ∩ E ′ ; C 1 , C 2 , . . . , C k be the resulting connected components of S ∩ E ′ ; 3. for i = 1, . . . , k -1, use an edge to link the last vertex of C i with the first vertex of C i+1 ; 4. output S ′ the solution so computed.

Obviously, in order that step 3 of A is able to link components C i and C i+1 , an edge must exist between the vertices implied; otherwise, A is definitely unfeasible. So, in order to assure feasibility, we make, for the rest of the section the basic assumption that the input graph for the problems tackled is complete.

In what follows, we denote by V [S ′ ] the set of vertices in S ′ and set

G ′′ (V [S ′ ], E ′′ ) = G[V [S ′ ]]
. Also, we denote by [v i , v j ] the set {v i+1 , v i+2 , . . . , v j-1 } (i < j in the ordering assumed for S) such that: (a) for any ℓ = i, i + 1, . . . , j -1, (v ℓ , v ℓ+1 ) ∈ S (i.e., [v i , v j ] is the set of vertices in the path linking v i to v j in S, where v i and v j themselves are not encountered3 ) and (b) v i and v j belong to consecutive4 connected subsets C m and C m+1 for some m < k.

Theorem 5. Consider a robust optimization problem robust Π verifying the following assumptions: (i) instances of Π are edge-valued complete graphs (K n , ℓ) = G(V, E, ℓ); furthermore, in the robust version of Π any vertex i ∈ V has a presence-probability p i ; (ii) a solution of Π is a subset S of E verifying some connectivity property; (iii) given an anticipatory solution S (the vertices of which are ranged in some appropriate order), algorithm A computes a feasible solution S ′ , for any subgraph

G ′ (V ′ , E ′ , ℓ) = G[V ′ ] of G (obviously, G ′ is complete); (iv) m(G, S) = (v i ,v j )∈S ℓ(v i , v j ).
Then, E(G, S) is computable in polynomial time and is expressed by: E(G, S)

= (v i ,v j )∈S ℓ(v i , v j )p i p j + (v i ,v j )∈E ′′ \S ℓ(v i , v j )p i p j v l ∈[v i ,v j ] (1 -p l ).
Proof. Denote by C[E ′ ], the set of edges added to S ′′ during the execution of step 3 of A. Obviously, S ′ = S ′′ ∪ C[E ′ ]; also, if an edge belongs to C[E ′ ], then it necessarily belongs to E[S], the set of edges in E induced by the endpoints of the edges in S. By assumptions (i) to (iii), S ′ is a feasible set of edges. Furthermore:

m G ′ , S ′ = (v i ,v j )∈E ℓ (v i , v j ) 1 {(v i ,v j )∈S ′ } = (v i ,v j )∈E ℓ (v i , v j ) 1 {(v i ,v j )∈S ′′ ∪C[E ′ ]} (15)
By construction, any element of C[E ′ ] is an edge (or arc) the initial endpoint of which corresponds to the terminal endpoint of a connected subset C i of S and the terminal endpoint of which corresponds to the initial endpoint of the "next" connected subset C i+1 of S. Then, for any subgraph G ′ of G, the following two assertions hold: (1) S ′ ⊆ E ′′ , and (2) any edge that does not belong to E ′′ , will never be part of any feasible solution. Indeed, for such an edge, at least one of its endpoints does not belong to V [S ′ ]; so, C[E ′ ] ⊆ E ′′ . We so have from ( 15):

m G ′ , S ′ = (v i ,v j )∈E ℓ (v i , v j ) 1 {(v i ,v j )∈S ′′ ∪C[E ′ ]} = (v i ,v j )∈E ′′ ℓ (v i , v j ) 1 {(v i ,v j )∈S ′′ ∪C[E ′ ]} = (v i ,v j )∈E ′′ ℓ (v i , v j ) 1 {(v i ,v j )∈S ′′ } + (v i ,v j )∈E ′′ ℓ (v i , v j ) 1 {(v i ,v j )∈C[E ′ ]} = (v i ,v j )∈S ℓ (v i , v j ) 1 {(v i ,v j )∈E ′ } + (v i ,v j )∈E ′′ \S ℓ (v i , v j ) 1 {(v i ,v j )∈C[E ′ ]} (16)

Application of Theorem 5 when the solution is a cycle

In this section, we consider min tsp and its robust version. Given a complete graph on n vertices, denoted by K n , with positive distances on its edges, min tsp consists of minimizing the cost of a Hamiltonian cycle (i.e., of an ordering v 1 , v 2 , . . . , v n of V such that v n v 1 ∈ E and, for 1 i < n, v i v i+1 ∈ E), the cost of such a cycle being the sum of the distances of its edges. We shall represent any Hamiltonian cycle T (called also a tour in what follows) as the set of its edges; its value is m(K n , T ) = e∈T ℓ(v i , v j ). Moreover, we arbitrarily number the vertices of K n in the order that they are visited in T ; so, we can set

T = {(v 1 , v 2 ), . . . , (v i , v i+1 ), . . . , (v n-1 , v n ), (v n , v 1 )}.
Consider an anticipatory tour T in an edge-valued complete graph K n and a set of absent vertices. Then, application of step 2 of A may result in a set {P 1 , P 2 , . . . , P k } of paths5 , ranged in the order vertices have been visited in T , that is not feasible for min tsp in the surviving graph. In order to render this set feasible, one can link (modulo k) the last vertex of the path P i to the first vertex of P i+1 ; this is always possible since the initial graph is complete. For example, in Figure 2(a), an anticipatory cycle T , derived from a (symmetric) K 8 is In Figure 2(b), we consider that vertices v 3 , v 4 , v 6 and v 8 are absent. In a first time, application of Step 2 of A results in a path-set {{(v 1 , v 2 )}, {v 5 }, {v 7 }}. In a second time, we will link vertex v 2 to v 5 (using dotted edge (v 2 , v 5 )) and vertex v 5 to v 7 (by dotted edge (v 5 , v 7 )). This creates a Hamiltonian path linking all the surviving vertices of the initial K 8 . Finally, we link vertex v 7 to v 1 (by the dotted edge (v 7 , v 1 )). We so build a new tour feasibly visiting all the present vertices of the remaining graph.

v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 (a) An anticipatory tour v 1 v 2 v 5 v 7 (
It is easy to see that for the case we deal with, all conditions of Theorem 5 are verified. Consequently, its application for the case of robust min tsp gives for E(K n , T ) the expression claimed in the theorem. We so recover the result of [START_REF] Jaillet | Probabilistic traveling salesman problem[END_REF] about robust min tsp. The anticipatory solution minimizing the functional cannot be characterized tightly by means of Theorem 5, since the expression for E(K n , T ) depends on the particular anticipatory tour T considered and by the way this particular tour will be completed in the surviving instance.

Application of Theorem 5 when the anticipatory solution is a tree

Let us now consider min spanning tree. Given an edge-valued graph G(V, E, ℓ), min spanning tree consists of determining a tree T spanning V and minimizing quantity e∈T ℓ(e). For reasons that will be understood later (see also [START_REF] Bertsimas | The probabilistic minimum spanning tree problem[END_REF]) we restrict ourselves to complete graphs. As previously in Section 5.1, we consider a by the set of its edges. For any tree T its value is m(K n , T ) = e∈T ℓ(v i , v j ).

Note that for robust min tsp in Section 5.1, its solution induces an implicit and natural ordering of the edges. This is not the case here since various orderings can be considered. We consider the one given by a kind of inverse depth-first-search (dfs) that goes as follows:

• starting from leaf numbered by 1 we first number its incident edge, then one of the edges intersecting it and so on, until we arrive to a second leaf;

• we then return back to the last vertex of the path incident to an edge not numbered yet and we continue the numbering from this edge until a third leaf is encountered;

we continue in this way until all the edges of T are visited.

This ordering is performed in O(n) for a tree of order n (recall that such a tree has n -1 edges). For example, consider the tree of Figure 3(a) and assume that it is a minimum spanning tree of some graph on 14 vertices. Starting from the leftmost leaf (numbered by 1) we visit edges (1, 2), (2, 3), . . . , [START_REF] Bertsimas | The probabilistic minimum spanning tree problem[END_REF][START_REF] Bertsimas | A priori optimization[END_REF] in this order; node 7 is another leaf. We then return to node 5 that is the last node incident to an edge not yet visited, and we visit edges (5, 8), (8, 9)(9, 10), [START_REF] Deȋneko | On the robust assignment problem under a fixed number of cost scenarios[END_REF][START_REF] Gupta | Boosted sampling: approximation algorithms for stochastic optimization[END_REF]. We then return to node numbered by 9 and visit edge [START_REF] Birge | Introduction to stochastic programming[END_REF][START_REF] Gupta | What about wednesday? approximation algorithms for multistage stochastic optimization[END_REF]. We return back to node numbered by 4 and visit edges (4, 13), [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] in this order. The ordering just obtained, partitions the edges of the tree into a number of edge-disjoint paths P 1 , P 2 , . . . For instance, dealing with Figure 3(a), the depicted tree T is partitioned into 4 paths: P 1 = {(1, 2), (2, 3), . . . , (6, 7)}, P 2 = {(5, 8), (8, 9)(9, 10), (10, 11)}, P 3 = {(9, 12)} and P 4 = {(4, 13), [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]}.

Suppose now that some vertices are absent from the initial graph G. Also, let us refer to the nodes by their numbering in the ordering just described. Then, step 2 of A will produce a non connected set of edges (forming paths, any of them being a subset of some P i ); denote by {P ′ 1 , P ′ 2 , . . . , P ′ k } the set of paths so-obtained. Order them paths following the order their edges appear in the inverse dfs paths of T . For any l = 1, . . . , k, we link the last vertex, say i of path P ′ l to the first vertex, say j, of the path P ′ l+1 . Since the initial graph is assumed complete, such an edge always exists.

Theorem 3 .

 3 If A achieves approximation ratio ρ for Π, then RA solves in polynomial time the robust version of Π within ratio O( √ ρn).

2 (

 2 b) Some "surviving" subgraph and the "surviving" solution

Figure 1 :

 1 Figure 1: An example for robust max cut.

Figure 2 :

 2 Figure 2: An example of application of algorithm A for robust min tsp.

Figure 3 :

 3 Figure 3: When anticipatory solution is a tree.

As we will see later such a modification strategy does not always produce feasible solutions; in such a case some more work is needed.

A property π is hereditary if, whenever is satisfied by a graph G, it is satisfied by any subgraph of G; a hereditary property π is non-trivial if it is true (satisfied) for infinitely many graphs and false for infinitely many graphs.

It is assumed that if [vi, vj] = ∅, then v l ∈[v i ,v j ] (1p l ) = 0.

With respect to the order C1, . . . , C k .

These paths may be sets of edges, or simple edges, or even isolated vertices, any such vertex considered as a path.

Summing inequality [START_REF] Gupta | What about wednesday? approximation algorithms for multistage stochastic optimization[END_REF] for j = 1, . . . , |S * 2 |, we get E(G[V 2 ], S * 2 ) n 2 /2n, where n 2 is the order of G[V 2 ]. On the other hand, using the leftmost upper bound in [START_REF] Bertsimas | The probabilistic minimum spanning tree problem[END_REF] we get E(G[V 2 ], S 2 ) n 2 p ′ . The bounds for E(G[V 2 ], S *

2 ) and E(G[V 2 ], S 2 ) immediately derive approximation ratio at most 2np ′ = O(np ′ ) and the proof of Claim 2 is complete.

We now turn to Claim Using the rightmost lower bound of ( 6), E(G[V 3 ], S * 3 ) |S * 3 |p ′ . On the other hand, by the rightmost upper bound of ( 6), E(G[V 3 ], S 3 ) |S 3 |. So, assuming that A achieves ratio ρ for Π, step 3 achieves ratio |S 3 |/|S * 3 |p ′ for G[V 3 ], that turns out to a ratio bounded above by ρ/p ′ , completing so the proof of Claim 3.

We prove that, for any k ∈ {1, 2, 3}:

In order to prove the first inequality, fix a k and consider a component, say V * j of S * . Then, the contribution of

, which is its contribution in S * . Iterating this argument for all the colors in C * [V k ], the claim follows.

Algorithm RA solves separately each G[V k ], k ∈ {1, 2, 3} and returns as solution S the union of the colors used. Hence,

So, the ratio of the algorithm in G is at most the sum of the ratios proved by Claims 1, 2 and 3, i.e., at most

Remark that the ratio claimed in Claim 2 is increasing with p ′ , while the one in Claim 3 is decreasing with p ′ . Equality of expressions np ′ and ρ/p ′ holds for p ′ = ρ/n. In this case the value of the ratio obtained is O( √ ρn), and the proof of the theorem is now complete.

Solutions are subsets of the initial edge-set

We deal in this section with problems for which solutions are sets of edges. Notice that whenever a vertex is absent from some subset V ′ ⊆ V , the edges incident to it are also absent from

So, our assumption is that, given a solution (in terms of a set of edges) S, and a set

The main result for this case, is the following theorem.

Then, the functional of robust Π is expressed as: E(G, S) = (v i ,v j )∈S ℓ(v i , v j )p i p j and can be computed in polynomial time. Furthermore, dealing with their respective computational complexities, robust Π and Π are equivalent.

Proof. Set S ′ = S ∩ E ′ ; by the assumptions of the theorem, S ′ is feasible for

:

Any edge (or arc) 16), we get:

As in the proof of Theorem 4, the first term of ( 17) can be simplified as follows:

Using ( 18) in ( 17), we get:

We now deal with the second term of ( 19) that, in this form seems to be exponential. Consider some edge (v i , v j ) added during step 3 in order to "patch", say connected components C l and C l+1 of the anticipatory solution S. Since (v i , v j ) / ∈ S, there exists in S a sequence µ = [v i , v j ] of consecutive edges (or arcs) linking v i to v j . Assume that this sequence is listed by its vertices and that neither v i , nor v j belong to µ. Edge i , v j ) ∈ E ′′ \ S ′ is added to S ′ just because all the vertices in µ are absent. In other words, inclusion

] is absent}. Consequently, the second sum in the second term of ( 19) can be written as:

Combination of ( 17), ( 19) and ( 20) derives the expression claimed for the functional. It is easy to see that computation of a single term in the second sum of the functional requires O(n) computations (at most n + 1 multiplications). Since we may do this for at most O(n 2 ) times (the edges in E), it ensues that the whole complexity of functional's computation is of O(n 3 ), that concludes the proof of the theorem. The fact that E(G, S) is polynomial is partly due to the same reasons as in Theorems 1 and 4. Furthermore, the order of the additional edges-choices in step 3 of A is also crucial for this efficience. Indeed, this order is such that one can say a priori under which conditions an edge (or arc) (v i , v j ) will be added in S ′ . These conditions carry over, the presence or the absence of the edges initially lying between v i and v j in S.

Unfortunately, in the opposite of Theorems 1 and 4, Theorem 5 does not derive a "good" characterization for the optimal anticipatory solutions of the problems meeting the assumptions (i) to (iv). In particular, the form of the functional does not imply solution of some well-defined weighted version of Π (the deterministic support of robust Π). Indeed due to the second term of the expression for E(G, S) in Theorem 5, the "costs" assigned to the edges depend on the structure of the anticipatory solution chosen.

In what follows, we outline some problems dealing with assumptions of Theorem 5. In particular, we tackle cases where feasible solutions are either cycles or trees.

We have now to explicit the path [i, j] associated with the edge (i, j) connecting P ′ l and P ′ l+1 . from T the edges of which are ordered as described, one can, w.l.o.g., renumber the vertices of the graph in such a way that T can be rewritten as T = {(1, 2), (2, 3), . . . , (nk, n)}. Then, T can be seen as a sequence of vertices some of them appearing more than once, i.e., T = (1 1 , 2 1 , 3 1 , . . . , j 1 , i 2 , (j + 1) 1 , . . . , (nk) q , n 1 ), where i < j and i c represents the c-th time node i is encountered in T . Based upon this representation, one can reconstruct T in the following way: for any pair (i c , j c ′ ) of consecutive vertices, edge (i, j) belongs to T if and only if i < j. Note that a leaf appears only once in the list.

Application of step 2 of A implies that, whenever an absent vertex v is not a leaf, its removal disconnects T . In order to reconnect it, must link the vertex preceding it in the sequence to the one succeeding it. By the particular form of the sequence considered, any edge (i, j) that algorithm A is likely to add in order to reconnect T is such that i < j; the corresponding path [i, j] (i.e., the of vertices that have to be absent in order that (i, j) is added), is the portion of the list between i l and j 1 , where i l is the last occurrence of i before the first occurrence j 1 of vertex j.

Let us revisit the example of Figure 3(a). The sequence associated with the tree is T = (1 1 , . . . , 7 1 , 5 2 , 8 1 , . . . , 11 1 , 9 2 , 12 1 , 4 2 , 13 1 , 14 1 ). Assume now that vertices 2, 5, 11 and 13 disappear from the initial graph. Application of step 2 of A results in the subsequence T ′ = (

). The first connected component (path) in this sequence is vertex 1 itself, and the second one is represented by nodes 3 and 4 (3 1 and 4 1 in T ′ ); we so add edge [START_REF] Averbakh | On the complexity of a class of combinatorial optimization problems with uncertainty[END_REF][START_REF] Bellalouna | Probabilistic combinatorial problems: a new domain in operational research[END_REF] in order to connect these two components. The third component is represented by vertices 6 and 7 (6 1 and 7 1 in T ′ ); edge (4, 6) is consequently added. The fourth connected component is induced by vertices 8, 9, 10 and 12 (8 1 , 9 1 , 10 1 , 9 2 , and 12 1 in T ′ ); hence, edge (7, 8) added. The fifth connected component in the sequence is vertex 4 itself (4 2 in T ′ ) but edge [START_REF] Gupta | What about wednesday? approximation algorithms for multistage stochastic optimization[END_REF][START_REF] Bertsimas | Probabilistic combinatorial optimization problems[END_REF] is not added because 12 > 4. Finally, the sixth connected component, vertex 14 (14 1 in T ′ ), entails introduction of edge (4, 14) that completes the modification of T by algorithm A. Denoting also by T the sequence of vertices representing the anticipatory spanning tree T and denoting any vertex of the initial graph by its numbering in the inverse dfs explained above, E(K n , T ) can be expressed as claimed by Theorem 5.

Final remarks

We have drawn a framework for the classification of robust problems under the a priori optimization paradigm. What seems to be of interest in this classification is that when restriction of the initial solution to the "present" subgraph is feasible, then the complexity of determining the optimal anticipatory solution for the problems tackled, amounts to the complexity of solving some weighted version of the deterministic problem, where the weights depend on the vertex-probabilities. These weights do not depend on particular characteristics of the anticipatory solution considered, thing that allows a compact characterization of optimal anticipatory solution. On the contrary, when more-than-one-stage algorithms are needed for building solutions, then the observation above is no more valid. In this case, one also recovers some weighted version of the original problem, but the weights on the data cannot be assigned independently of the structure of a particular anticipatory solution.