Giorgio Ausiello
email: ausiello@dis.uniroma1.it.

Bruno Escoffier
email: escoffier@lamsade.dauphine.fr.

Jérôme Monnot
email: monnot@lamsade.dauphine.fr.

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

Reoptimization of minimum and maximum traveling salesman's tours

In this paper, reoptimization versions of the traveling salesman problem (TSP) are addressed. Assume that an optimum solution of an instance is given and the goal is to determine if one can maintain a good solution when the instance is subject to minor modifications. We study the case where nodes are inserted in, or deleted from, the graph. When inserting a node, we show that the reoptimization problem for MinTSP is approximable within ratio 4/3 if the distance matrix is metric. We show that, dealing with metric MaxTSP, a simple heuristic is asymptotically optimum when a constant number of nodes are inserted. In the general case, we propose a 4/5-approximation algorithm for the reoptimization version of MaxTSP.

Introduction

The traveling salesman problem (TSP) is one of the most interesting and paradigmatic optimization problems. In both minimization and maximization versions, TSP has been widely studied and a large bibliography is available (see, for example, the books [START_REF] Gutin | The Traveling Salesman Problem and Its Variations[END_REF][START_REF] Johnson | The traveling salesman problem : a case study[END_REF][START_REF] Lawler | The Traveling Salesman Problem: a guided tour of Combinatorial Optimization[END_REF]). As it is well known, both versions of TSP are NP-hard but although in the case of MaxTSP the problem is approximable within constant ratio for all kinds of graphs [START_REF] Chen | Improved deterministic approximation algorithms for Max TSP[END_REF][START_REF] Hassin | A 7/8-approximation algorithm for metric Max TSP[END_REF], in the case of MinTSP approximation algorithms are known only for the metric case [START_REF] Christofides | Worst-case analysis of a new heuristic for the traveling salesman problem[END_REF], i.e., when the graph distances satisfy the triangle inequality.

In this paper, we deal with reoptimization issue. We consider the case where instances of a given optimization problem are subject to minor modifications. The problem we are interested in consists, given an optimum solution on the initial instance, of trying to maintain efficiently a good solution when the instance is slightly modified. This issue has already been studied for other optimization problems such as scheduling problems (see [START_REF] Schäffter | Scheduling with forbidden sets[END_REF][START_REF] Bartusch | Scheduling project networks with resource constraints and time windows[END_REF], or [START_REF] Bartusch | A conceptional outline of a dss for scheduling problems in the building industry[END_REF] for practical applications) and classical polynomial problems where the goal is to recompute the optimum solution as fast as possible ( [START_REF] Eppstein | Sparsification -a technique for speeding up dynamic graph algorithms[END_REF][START_REF] Henzinger | Maintaining minimum spanning trees in dynamic graphs[END_REF]). It has been recently considered for MinTSP in [START_REF] Archetti | Reoptimizing the traveling salesman problem[END_REF]. The modifications for TSP consists in adding a new node to the initial graph (we have a new city to visit), or removing one node from this graph (a city is dropped from the tour).

More precisely, we suppose that an n node graph G is given and an optimum solution of MinTSP for G has already been computed. In the problem-version we deal with, denoted MinTSP+ in the sequel, G is transformed into a graph G ′ by adding a new node v n+1 together with all edges connecting v n+1 to any node of G. How can we reuse the known optimum solution of MinTSP for G in order to compute a good approximate solution for G ′ ? An analogous problem denoted MinTSP-consists of reoptimizing MinTSP when a node v in G is deleted together with all edges incident to it. In [START_REF] Archetti | Reoptimizing the traveling salesman problem[END_REF], Archetti, Bertazzi and Speranza show that both MinTSP+ and MinTSP-are NP-hard. Moreover they prove that if the simple best insertion rule is used for updating the previously known optimum tour, a (tight) 3/2 approximate tour for MinTSP+ in metric case can be obtained whereas in the general case, they propose some instances leading to the claim that best insertion rule is not a constant approximation; the same (tight) 3/2 approximation ratio is obtained for MinTSP-in the metric case. In their paper, the authors of [START_REF] Archetti | Reoptimizing the traveling salesman problem[END_REF] were mainly motivated by the situation where a short amount of time is available for the reoptimization. However, another interesting question is to know if the knowledge of an optimum solution for a part of the input graph leads to strictly better approximation ratios for the whole of the graph than those achieved in the classical approximation framework.

In this paper we provide new insights for the reoptimization of MinTSP (for metric graphs), both in the case of a single update and in the case where k new nodes are inserted (denoted MinTSP+k). For MinTSP+ in metric case we show that by combining the best insertion heuristics with Christofides' algorithm the result of [START_REF] Archetti | Reoptimizing the traveling salesman problem[END_REF] can be outperformed, by achieving approximation ratio 4/3. Moreover, it is possible to show that, for any k, MinTSP+k can be approximated asymptotically better than 3/2, although, for large values of k, the approximation ratio converges to Christofides' bound. On the other hand, dealing with the general case, we prove that MinTSP+ is not constant approximable. We also study reoptimization of MaxTSP, by considering the problems MaxTSP+ and MaxTSP+k for the first time, both in the metric and in the general case (note that these problems are obviously NP-hard). In particular we show that, in the metric case, for any k, the best insertion rule is asymptotically optimum; in fact, for any k, MaxTSP+k can be approximated with ratio 1 -O(k) √ n . In the general case we can exhibit a 4/5-approximation algorithm, an improvement over the approximation ratio 61/81, achieved in [START_REF] Chen | Improved deterministic approximation algorithms for Max TSP[END_REF] (under the classical approximation paradigm). The paper is organized as follows. In the next section, we provide basic definitions and notation. In Section 3, we address the reoptimization of MinTSP under single and multiple node insertions. Next, in Section 4, we consider the reoptimization of MaxTSP, first under single node insertion (both in the metric and in the general case) and subsequently under multiple insertions (in the metric case). Finally, in Section 5, some results concerning MinTSP-and MaxTSP-are provided. Concluding remarks are contained in Section 6.

All the missing and sketched proofs are given in the appendix.

In this section we provide the formal definitions of the problems addressed in the paper, namely Min and MaxTSP+k, Min and MaxTSP-k. Then, we introduce three heuristics, Best Insertion, Longest Insertion, and Nearest Insertion, classically studied in the literature (see for instance [START_REF] Rosenkrantz | An analysis of several heuristics for the traveling salesman problem[END_REF][START_REF] Gutin | The Traveling Salesman Problem and Its Variations[END_REF]) because they give rise to fast algorithms to solve TSP, and particularly suitable when dealing with reoptimization.

Definition 1 (MinTSP+k, MaxTSP+k). We are given an instance (I n+k , T * n ) where

I n+k = (K n+k , d), K n+k is a complete graph on n+k nodes {v 1 , • • • , v n+k },
I n = (K n , d), sub-instance of I n+k induced by the nodes {v 1 , • • • , v n }.
For the case k = 1, we simply denote the problems MinTSP+, MaxTSP+, Min TSP-and MaxTSP-.

For TSP, a particular rapid way to get a tour is to iteratively insert nodes according to given rules, as the following classical ones. Definition 3 (Nearest, Longest and Best Insertion rule). Given a tour T on a graph G = [V, E], and a node v ∈ V , we insert v in the sequence of nodes of T as follows:

-Nearest Insertion: we find a node v * minimizing d(u, v) for u ∈ V , and insert v before or after v * (choosing the best solution) in the tour; -Longest Insertion: we find a node v * maximizing d(u, v) for u ∈ V , and insert v before or after v * (choosing the best solution) in the tour; -Best Insertion: we find an edge (u * , v * ) ∈ T optimizing (d(v, u) + d(v, w)d(u, w)) for (u, v) ∈ T , and insert v between u * and v * .

Concerning polynomial approximation of MinTSP in the metric case, it is shown in [START_REF] Rosenkrantz | An analysis of several heuristics for the traveling salesman problem[END_REF] that the behavior of Nearest and Best Insertions are quite different since the algorithms based on these two rules are a 2 and a O(log n) -approximation respectively.

Finally, when nodes are deleted, the most natural way to get a solution from a tour on the initial instance consists in taking the shortcut. Definition 4 (Deletion). Given a tour T on a graph G = [V, E], and a node v ∈ V , deletion consists in building a tour by deleting v in T (removing (u, v) and (v, w) from T and adding (u, w)).

Reoptimizing minimum TSP under node insertions

In this section, we study the reoptimization problems where one node is inserted (MinTSP+) and several nodes are inserted (MinTSP+k). We show that we can improve the result of [START_REF] Archetti | Reoptimizing the traveling salesman problem[END_REF] proving that, in the metric case, MinTSP+ is approximable within ratio 4/3.

On the contrary, if the distance is not assumed to be metric, then the knowledge of an optimum solution in the initial instance is not useful at all in order to find an approximate solution of the final instance since MinTSP+ (and consequently MinTSP+k) is not constant approximable (unless P =NP).

Finally, we generalize the result in the metric case by showing that when k nodes are inserted we get a (3/2 -1/(4k + 2))-approximation algorithm.

One node insertion

When dealing with metric instances of MinTSP+, it is proved in [START_REF] Archetti | Reoptimizing the traveling salesman problem[END_REF]

, v n+1 ) = min{d(v i , v n+1 ) : i = 1, • • • , n}. Thus d(T 1 ) ≤ d(T * n+1 ) + 2 max{d(v i , v n+1 ), d(v j , v n+1 )} (1)
Now, consider the algorithm of Christofides ([5]) applied on I n+1 . This gives a tour T 2 of length at most 1/2d(T * n+1 ) + M ST (I n+1 ), where M ST (I n+1 ) is the value of a minimum spanning tree on

I n+1 . Note that M ST (I n+1 ) ≤ d(T * n+1 ) - max(d(v i , v n+1 ), d(v j , v n+1 )). Hence : d(T 2 ) ≤ 3 2 d(T * n+1 ) -max(d(v i , v n+1 ), d(v j , v n+1 )) (2)
We take the best solution between T 1 and T 2 . A combination of equations ( 1) and ( 2) with coefficients 1 and 2 gives the expected result.

Obviously, if we apply Best Insertion instead of Nearest Insertion, the same result holds. Note that the running time of this algorithm is dominated by the one of Christofides' algorithm.

⊓ ⊔

In [START_REF] Archetti | Reoptimizing the traveling salesman problem[END_REF], it is shown that if the distance is not assumed to be metric, then Best Insertion is not constant approximate for MinTSP+. We strengthen this result by proving that this holds for any polynomial algorithm.

To do this, we need an intermediate result. Given a graph G = [V, E] where a, b, s, t ∈ V , and an hamiltonian path of G from a to b, we consider the problem of determining if there exists an hamiltonian path from s to t. Using a slight modification of the result of [START_REF] Papadimitriou | Some complexity results for the traveling salesman problem[END_REF], we can show that this problem, denoted by SHP a,b,s,t in the sequel, is NP-complete (see appendix).

Lemma 1. SHP a,b,s,t is NP-complete (even in bipartite graphs of maximum degree 5).

This lemma leads to the following inapproximability result.

Theorem 2. In the general case, MinTSP+ is not 2 p(n) -approximable, if P =NP, for any polynomial p.

Proof. We apply the general method described in [START_REF] Sahni | P-complete approximation problems[END_REF]. Let ρ > 1. We start from an instance of SHP a,b,s,t , i.e. a graph G n = [V, E] with n nodes, four nodes a, b, s, t, and an hamiltonian path P from a to b. We construct an instance (I n+1 , T * n ) in the following way:

• If (v i , v j ) ∈ E, then d(v i , v j ) = 1. • d(a, b) = 1 and d(v n+1 , s) = d(v n+1 , t) = 1.
• All the other edges have a weight ρ(n + 1) + 1.

It is clear that

T * n = P ∪ {(a, b)} is an optimum solution of I n = (K n , d) with cost d(T * n ) = n. Thus, (I n+1 , T * n ) is an instance of MinTSP+. Let T * n+1
be an optimum solution of (K n+1 , d). Remark that any ρ-approximate solution allows us to decide if d(T * n+1 ) = n + 1. However d(T * n+1 ) = n + 1 iff there is a hamiltonian path from s to t in G n . Setting ρ = 2 p(n) , we obtain the claimed result.

⊓ ⊔

k node insertions

When k nodes are inserted, we can generalize the result of Theorem 1 in the following way.

Theorem 3. In the metric case, MinTSP+k is approximable within ratio 3/2 -1/(4k + 2)

Proof. Consider the given optimum solution T * n . We apply Nearest Insertion with a priority rule. In a first step, we sort the vertices to be inserted (and relabel them) in such a way that for all p > n, there exists v j , j < p such that

d(v p , v j ) = min{d(v i , v l ) : i ≥ p, l < p}. Note that d(v p , v j ) ≤ d max (T * n+k )
, where d max (T * n+k ) is a maximal weighted edge in T * n+k . Then we insert the k vertices using Nearest Insertion. For the analysis, note that when inserting vertex v p , we increase the distance by ∆ p ≤ 2d(v p , v j ) ≤ 2d max (T * n+k ). We finally get an approximate solution T 1 such that

d(T 1 ) ≤ d(T * n ) + 2kd max (T * n+k ) ≤ d(T * n+k ) + 2kd max (T * n+k ) (3)
Christofides' algorithm gives a solution T 2 such that

d(T 2 ) ≤ 3 2 d(T * n+k ) -d max (T * n+k ) (4)
We take the best solution between T 1 and T 2 . A combination of equations ( 3) and ( 4) with coefficients 1 and 2k gives d(T )

≤ 3 2 -1 4k+2 d(T * n+k ). Note that the computation time of T 1 is O(k(n + k))
, hence the global complexity is dominated by running Christofides' algorithm.

⊓ ⊔

Reoptimizing maximum TSP under node insertions

In this section, we consider the reoptimization of the maximization version of TSP. In the metric case, Best Insertion is a very good strategy since it is asymptotically optimum. Note that the usual MaxTSP problem in the metric case does not admit a PTAS (using [START_REF] Papadimitriou | The traveling salesman problem with distances one and two[END_REF]) and that the best algorithms for it are asymptotically 17/20 (deterministic, [START_REF] Chen | Improved deterministic approximation algorithms for Max TSP[END_REF]) and 7/8 (randomized, [START_REF] Hassin | A 7/8-approximation algorithm for metric Max TSP[END_REF]). If the distance is not assumed to be metric, the situation is a bit more complicated. Longest and Best Insertion are only a 1/2-approximation. This situation is quite disappointing since we can easily prove that iterating Longest Insertion (from the empty graph) with a priority rule is already a 1/2-approximation for MaxTSP; however, we can get a polynomial algorithm achieving a ratio of 4/5. This shows that the knowledge of an optimum solution on the initial instance is useful since the best algorithm for the usual MaxTSP achieves an approximation ratio of 61/81 ( [START_REF] Chen | Improved deterministic approximation algorithms for Max TSP[END_REF]).

Finally, in section 4.2, we generalize the result in the metric case showing that if we insert a constant number on nodes, then iterating Best Insertion is also an asymptotically optimum strategy.

Note that the NP-hardness of all these problems is obvious since otherwise, starting from the empty graph, we could solve polynomially MaxTSP.

One node insertion

The central result of this section is the asymptotical optimality of Best Insertion.

. Let K = √ n and 1 ≤ k ≤ K.
Consider the following subsequence of nodes (a k ,

• • • , a 1 , v n+1 , b 1 , • • • , b k ) in T * n+1 . Let J k be the sub-instance of I n+1 induced by all the nodes but v n+1 , a 1 , a 2 , • • • , a k-1 and b 1 , b 2 , • • • , b k-1 (in particular J 1 is (K n , d), the initial graph).
We have :

d(T * n+1 ) ≤ d(v n+1 , a 1 ) + d(v n+1 , b 1 ) + k-1 i=1 d(a i , a i+1 ) + k-1 i=1 d(b i , b i+1 ) + opt(J k )
where opt(J k ) is the value of an optimum solution on J k . Indeed, there is an hamiltonian path in T * n+1 between a k and b k , the value of which is at most opt(J k ).

Let d k m (v) be the medium distance between a node v and the nodes in

J k , i.e., d k m (v) = 1 |J k | vi∈J k d(v, v i ).
Using the triangle inequality, we get that for any pair (u, v) of nodes (and for any k

), d(u, v) ≤ d k m (u) + d k m (v).
Hence we get an upper bound on d(T * n+1 ):

d(T * n+1 ) ≤ 2 d k m (n + 1) + k-1 i=1 d k m (a i ) + k-1 i=1 d k m (b i ) +d k m (a k )+d k m (b k )+opt(J k )
(5) Now, our goal is to lower bound first d(T * n ) and then d(T ) in order to get the following inequality :

d(T ) ≥ 1 - O(k) n (d(T * n+1 ) -d k m (a k ) -d k m (b k )) (6)
To achieve this, first consider an optimum solution

T * (J k ) (of value opt(J k )) of J k . Considering a particular subsequence (v 1 , • • • , v 2k-1 ) of T * (J k ), we insert the 2(k -1) nodes a 1 , a 2 , • • • , a k-1 and b 1 , b 2 , • • • , b k-1 in T * (J k ) in order to get the sequence (v 1 , a 1 , • • • , a k-1 , v k , b 1 , • • • , b k-1 , v 2k-1
). Considering each node of J k as v 1 , we get with these insertions n -2(k -1) tours on I n . After a careful counting of the edges appearing in these tours, one can show that:

d(T * n ) ≥ 2 k-1 i=1 d k m (a i ) + k-1 i=1 d k m (b i ) + 1 - O(k) n opt(J k ) (7)
Now, we relate d(T ) and d(T * n ). Consider each of the n possible insertions of v n+1 in T * n . Since each edge of T * n is removed exactly once, we get that nd(T ) ≥

(n -1)d(T * n ) + 2 n i=1 d(v n+1 , v i ). Using n i=1 d(v n+1 , v i ) ≥ v∈J k d(v n+1 , v) = (n -2(k -1))d k m (n + 1)
, we get:

d(T ) ≥ 1 - 1 n d(T * n ) + 2 1 - 2(k -1) n d k m (n + 1) (8)
From inequalities ( 5), ( 7) and ( 8), we can derive [START_REF] Eppstein | Sparsification -a technique for speeding up dynamic graph algorithms[END_REF].

Inequality ( 6) is valid for any k. Let us write it for k = 1, • • • , K, and consider the two following cases :

1. If, for some k, d k m (a k ) + d k m (b k ) ≤ 1 K d(T * n+1
), then we get

d(T ) ≥ 1 - O(k) n 1 - 1 K d(T * n+1 ) Since k ≤ K = √ n, we get d(T ) ≥ 1 -O 1 √ n d(T * n+1 ). 2. In the other case, for any k, d k m (a k ) + d k m (b k ) ≥ 1 K d(T * n+1
). However, this is impossible. Indeed, by making the sum, we get

K k=1 d k m (a k ) + d k m (b k ) ≥ d(T * n+1
). But (details are omitted here), one can show that this would lead to

d(T * n ) ≥ 2 1 -O(K) n d(T * n+1
), which is impossible for n large enough.

✷

From Theorem 4, we get the following corollary.

Corollary 1. MaxTSP+ admits a PTAS in the metric case.

Proof. Let ε > 0. To get a (1 -ε)-approximation algorithm, we just have to apply Best Insertion on graphs with roughly n ≥ O(1/ε 2 ) nodes, and to solve optimally the other instances.

⊓ ⊔

Unfortunately, if the triangle inequality is not assumed, Best Insertion has a much worse behavior (see appendix).

Proposition 2. For MaxTSP+, in the general case, Best Insertion and Longest Insertion give a 1/2-approximation, and this bound is tight (even if the graph has an arbitrary large number of nodes).

However, we can use a more sophisticated algorithm to get a better approximation ratio.

Theorem 5. MaxTSP+ is asymptotically approximable within ratio 4/5. Proof (Sketch). Assume n even; thus T * n is the sum of two perfect matchings M 1 and M 2 (if n is odd we can add the remaining edge to each matching. Details are omitted). Suppose d(M 1 ) ≥ d(M 2 ). We get:

d(M 1 ) ≥ 1 2 d(T * n ) (9)
Let v i and v j be the neighbors of v n+1 in T * n+1 . Consider M * = M 1 ∪ {(v i , v n+1 ), (v n+1 , v j )}. Obviously, M * can be found in polynomial time by guessing nodes v i and v j . Wlog., we can assume that M * does not contain any cycle (otherwise, (v i , v j ) ∈ T * n and thus Best Insertion gives an optimum tour). Now, consider C = {C 1 , • • • , C p }, a 2-matching (i.e., a partition of {v 1 , • • • , v n+1 } into node disjoint cycles) of maximum weight among the 2-matchings satisfying (i) {(v i , v n+1 ), (v n+1 , v j )} ⊂ C 1 and (ii) |C 1 | ≥ 6. Such a 2-matching can be found in polynomial time by testing all the possible subsequences of nodes (v i ′′ , v i ′ , v i , v n+1 , v j , v j ′ ) (and thanks to the polynomiality of finding a maximum weight 2-matching, [START_REF] Hartvigsen | Extensions of Matching Theory[END_REF]). Obviously, we deduce:

d(C) ≥ d(T * n+1 ) (10)
Applying the method of Serdyukov [START_REF] Serdyukov | An algorithm with an estimate for the traveling salesman problem of the maximum[END_REF], we can iteratively for i = 1, • • • , p, delete an edge e i ∈ C i , and add this edge to M * in such a way that M * does not contain any cycle. Note that in this method we can chose in C 1 a deleted edge not in M * that does not create a cycle in P 1 (thanks to the length of C 1 ).

At the end, P 1 = ∪ p i=1 (C i \ {e i }) and P 2 = M * ∪ p i=1 {e i } are two collection of node disjoint paths. Finally, we build two tours T 1 and T 2 by adding some edges to P 1 and P 2 respectively. Taking the best tour, and using inequalities ( 9) and ( 10), we get a tour T 3 with:

d(T 3 ) ≥ 3 4 d(T * n+1 ) + 1 4 (d(v i , v n+1 ) + d(v n+1 , v j )) (11)
On the other hand, the Best Insertion gives a tour T 4 verifying:

d(T 4 ) ≥ n -1 n d(T * n ) ≥ n -1 n d(T * n+1 ) - n -1 n (d(v i , v n+1 ) + d(v n+1 , v j )) (12)
Adding inequality [START_REF] Henzinger | Maintaining minimum spanning trees in dynamic graphs[END_REF] with coefficient (n -1)/n and inequality (12) with coefficient 1/4 we obtain a tour satisfying d(T ) ≥ 4n-4 5n-4 d(T * n+1 ). ✷

k node insertions

When several nodes are inserted, we can iteratively use the Best Insertion rule to obtain an asymptotically optimum solution. This result is based on the following lemma.

Lemma 2. If T n is a ρ-approximation on the initial instance on n nodes G n , then Best Insertion applied on T n gives a ρ 1 -O(1) √ n -approximate solution (in the metric case) on the instance G n+1 on n + 1 nodes. Proof (Sketch). This is an easy generalization of the proof of theorem 4. Note that equation ( 5) and (7) still hold. Then, by taking into account that T n is a ρ-approximation, we get, instead of equation ( 6):

d(T ) ≥ ρ 1 - O(k) n (d(T * n+1 ) -d k m (a k ) -d k m (b k )) (13)
The end of the proof is analogous, up to the factor ρ. ✷ Theorem 6. Iterated Best Insertion is a 1 -O(k) √ n -approximation algorithm for MaxTSP+k in the metric case.

Proof. Using proposition 2, we get, after k steps, a solution T k such that:

d(T k ) ≥ 1 - O(1) √ n k d(T * n+k ) ≥ 1 - O(k) √ n d(T * n+k ) ⊓ ⊔
Using a similar proof as in corollary 1, we easily get the following result.

Corollary 2. For any constant k (and even for any k = o( √ n)), MaxTSP+k admits a PTAS in the metric case.

Node deletions

Now, we give a few results concerning the reoptimization problems when nodes are deleted from the initial graph. Recall that in [START_REF] Archetti | Reoptimizing the traveling salesman problem[END_REF] it is shown that MinTSPis NP-hard, even if distances are only 1 and 2, and that deletion is a tight 3/2approximation in the metric case. Here, we show that MinTSP-is very hard to approximate if the triangle inequality doesn't not hold. Dealing with MaxTSP-, we show that the problem is NP-hard, and that deletion is a tight 1/2-approximation algorithm (general and metric cases). Proposition 3. In the general case, MinTSP-is not 2 p(n) -approximable, if P =NP, for any polynomial p.

Proof. The proof is a direct adaptation of the one of [START_REF] Archetti | Reoptimizing the traveling salesman problem[END_REF] showing that this problem is NP-hard. We consider the following problem, shown to be N P -complete in [START_REF] Papadimitriou | Some complexity results for the traveling salesman problem[END_REF]: given a graph G = [V, E] and an hamiltonian path P between two nodes a and b in G, determine if there's an hamiltonian cycle in G.

Given such an instance, we construct an instance on MinTSP-. The node set of the graph K n+1 is V ∪ {v n+1 }, and the distances are:

-d(v i , v j ) = 1 if (v i , v j ) ∈ E; -d(v n+1 , a) = d(v n+1 , b) = 1; -Other distances are ρn + 1. The tour T * n+1 = P ∪ {(v n+1 , a), (v n+1 , b)} is an optimum solution on I n+1 = (K n+1 , d). Let T *
n be an optimum solution on the instance I n . Then d(T * n ) = n iff G has an hamiltonian cycle, and a ρ approximate solution allows to decide if d(T * n ) = n. We get the lower bound setting ρ = 2 p(n) . ⊓ ⊔ Proposition 4. MaxTSP-is N P -hard, even if distances are only 1 and 2.

Proof. In [START_REF] Archetti | Reoptimizing the traveling salesman problem[END_REF], it is shown that MinTSP-is N P -hard, even if distances are only 1 and 2. We have a trivial reduction from MinTSP-to MaxTSP-if distances are only 1 and 2: we just have to flip the distances between 1 and 2. Solving MinTSP-is equivalent to solve MaxTSP-with the new distances.

⊓ ⊔

As a final result, let us remark that the deletion strategy has the same behavior in the metric case and in the general one (see appendix for the proof).

Proposition 5. For MaxTSP-, deletion gives a 1/2-approximation, and this bound is tight (even if the graph has an arbitrary large number of nodes). These results hold in the general case as well as in the metric case.

These results might be strengthened, but they seem to indicate that the knowledge of an optimum solution in the initial instance may not be really helpful to get good approximation ratios when nodes are deleted.

Conclusion

In this article we have proposed some complexity and approximability results for reoptimization versions of TSP. We have exhibited an interesting asymmetry between the maximization and the minimization versions: while we get an almost optimum tour by simply inserting the new node in the right position for MaxTSP+ (in the metric case), this is not true when dealing with the minimization version. One can even show that in order to get an almost optimum solution for MinTSP+, we need, on some instances, to change n -o(n) edges from the initial optimum solution. This leads us to conjecture that MinTSP+ does not admit a PTAS.

Following our approach, an interesting generalization would be to consider TSP in a fully dynamic situation. Starting from a given solution (optimum or approximate) on an initial graph, the graph evolves (nodes are added and deleted), and the goal is to maintain efficiently, along this process, an approximate solution as good as possible. Some of our results can be easily generalized when starting from an approximate (instead of optimum) solution, and can be useful in such approach. Finally, we connect the copies together in the following way:

• We add the edge set E 2 = {(a L i , a R i+1 ) : i = 1, . . . , n -1}. • If (v i , v j ) ∈ E, then we add edges (v R i , v L j ) and (v L i , v R j ).
From this construction we can observe that any hamiltonian path of H must traversed each copy H i in one of the two following ways: either P 1,i or P 2,i (see Figure 2).

The resulting graph is bipartite (each copy H i is bipartite and a left node v L i is only connected to a right node v R j ) of maximum degree 5 and the edge set P * = E 2 ∪ n i=1 P 2,i induces an hamiltonian path from a R 1 to a L n in H. We claim that G has an hamiltonian path from v 1 to v n iff H has an hamiltonian path from v L 1 to v R n . Let P = (v i1 , . . . , v in ) with i 1 = 1 and i n = n be an hamiltonian path of G. We build the hamiltonian path

P ′ from v L 1 to v R n in H using the set of paths ∪ n i=1 P 1,i and the edge set {(v R ij , v L ij+1 ) : j = 1, . . . , n -1}. Conversely, let P ′ be an hamiltonian path from v L 1 to v L n in H.
Using the previous property of H i , we deduce that P ′ must contain all the paths P 1,i for i = 1, . . . , n. Thus, the edge set

P = {(v i , v j ) : (v R i , v L j ) ∈ P ′ } is an hamiltonian path from v 1 to v n . ⊓ ⊔ P 1,i v L i v R i a R i a L i v L i v R i a R i a L i P 1,2
Fig. 2. The two graph hamiltonian path P1,i and P2,i of Hi.

Proof of Proposition 1:

Let v i1 and v j1 be the neighbors of v * in T * n and let v i and v j be the neighbors of v n+1 in T * n+1 . By construction of Longest Insertion rule, the produced solution T 1 verifies:

2d(T 1 ) ≥ 2d(T * n )+2d(v * , v n+1 )+d(v i1 , v n+1 )+d(v j1 , v n+1 )-d(v i1 , v * )-d(v j1 , v * ) (14)
Let us prove that we also have:

d(T 1 ) ≥ 1 2 d(T * n+1 ) + 1 2 (d(v i , v n+1 ) + d(v j , v n+1 )) (15)
Consider the two cases:

• v * / ∈ {v i , v j }; when we walk around T * n from v i1 , v * , v j1 , assume that we met v j and v i in this order. Thus, using the triangle inequality we deduce:

d(T * n ) ≥ d(v i1 , v * ) + d(v * , v j1 ) + d(v j1 , v j ) + d(v i , v i1 ) (16)
The inequality (15) holds using inequalities ( 14), [START_REF] Rosenkrantz | An analysis of several heuristics for the traveling salesman problem[END_REF], and the triangle inequality.

• v * ∈ {v i , v j }; assume v * = v i . In this case, we deduce d(T * n ) ≥ d(v i1 , v i ) + d(v i , v j1 ) + d(v j1 , v j ) + d(v j , v i1
) and the inequality (15) also holds.

On the other hand, using the triangle inequality we also get:

d(T 1 ) ≥ d(T * n ) ≥ d(T * n+1 ) -d(v i , v n+1 ) -d(v j , v n+1 ) (17)
Adding inequality [START_REF] Papadimitriou | The traveling salesman problem with distances one and two[END_REF] with coefficient 2 and inequality [START_REF] Sahni | P-complete approximation problems[END_REF], the expected result follows.

In order to show the tightness, consider (I n+1 , T * n ) where

d(v n+1 , v n ) = n+ 1, d(v n+1 , v i ) = n, ∀i = 1, • • • , n -1, d(v n , v i ) = 2n, ∀i = 1, • • • , n -1, and d(v i , v j ) = 0, ∀i, j 1 ≤ i < j ≤ n -1. The tour T * n is given by the se- quence (v 1 , v 2 , • • • , v n , v 1 ). Longest Insertion on T * n gives d(T 1 ) = 4n + 1 whereas d(T * n+1 ) = 6n. ⊓ ⊔
Complete proof of Theorem 4:

Proof. Let T * n be an optimum solution on the initial instance I n , T * n+1 an optimum solution on the final instance I n+1 , and T the solution obtained by applying Best Insertion on T * n . Let K = √ n and 1 ≤ k ≤ K.

Consider the following subsequence of nodes (a k ,

• • • , a 1 , v n+1 , b 1 , • • • , b k ) in T * n+1 .
Let J k be the sub-instance of I n+1 induced by all the nodes but v n+1 ,

a 1 , a 2 , • • • , a k-1 and b 1 , b 2 , • • • , b k-1 (in particular J 1 is (K n , d), the initial in- stance).
We have :

d(T * n+1 ) ≤ d(v n+1 , a 1 ) + d(v n+1 , b 1 ) + k-1 i=1 d(a i , a i+1 ) + k-1 i=1 d(b i , b i+1 ) + opt(J k )
where opt(J k ) is the value of an optimum solution on J k . Indeed, there is an hamiltonian path in T * n+1 between a k and b k , the value of which is at most opt(J k ).

Let d k m (v) be the medium distance between a node v and the nodes in

J k , i.e., d k m (v) = 1 |J k | vi∈J k d(v, v i ).
Using the triangle inequality, we get that for any pair (u, v) of nodes (and for any k), d(u, v) ≤ d k m (u) + d k m (v). Hence we get an upper bound on d(T * n+1 ):

d(T * n+1 ) ≤ 2 d k m (n + 1) + k-1 i=1 d k m (a i ) + k-1 i=1 d k m (b i ) +d k m (a k )+d k m (b k )+opt(J k ) (18
) Now, our goal is to lower bound first d(T * n ) and then d(T ) in order to get the following inequality :

d(T ) ≥ 1 - O(k) n (d(T * n+1 ) -d k m (a k ) -d k m (b k )) (19)
To achieve this, first consider an optimum solution T * (J k ) (of value opt(J k )) of J k . Consider a particular node v 1 in J k , and let us call v 2 , • • • , v 2k-1 the nodes following v 1 in T * (J k ) (given an arbitrary order). We insert the 2(k -1) nodes

a 1 , a 2 , • • • , a k-1 and b 1 , b 2 , • • • , b k-1 in T * (J k ) in the following way: v 1 , a 1 , v 2 , a 2 , ..., v k-1 , a k-1 , v k , b 1 , v k+1 , ..., b k-1 , v 2k-1
Hence we get a tour on I n . We apply this construction n -2(k -1) times, considering for v 1 all the nodes in J k . Then we get n -2(k -1) tours on I n . However, for each node v of J k and each a i , the edge (a i , v) appears twice (the same holds for (b i , v)). Moreover, each edge of T * (J k ) is removed 2(k -1) times, hence appears n-2(k -1)-2(k -1) times. This leads to the following inequality:

(n -2(k -1))d(T * n ) ≥ 2(n -2(k -1)) k-1 i=1 d k m (a i ) + k-1 i=1 d k m (b i ) +(n -2(k -1) -2(k -1))opt(J k ) d(T * n ) ≥ 2 k-1 i=1 d k m (a i ) + k-1 i=1 d k m (b i ) + 1 - 2(k -1) n -2(k -1) opt(J k ) (20) Considering that k ≤ √ n: d(T * n ) ≥ 2 k-1 i=1 d k m (a i ) + k-1 i=1 d k m (b i ) + 1 - O(k) n opt(J k ) (21)
Now, we relate d(T ) and d(T * n ). Consider each of the n possible insertions of v n+1 in T * n . Since each edge of (T * n ) is removed exactly once, we get:

nd(T ) ≥ nd(T * n ) + 2 n i=1 d(v n+1 , v i ) -d(T * n ) However n i=1 d(v n+1 , v i ) ≥ v∈J k d(v n+1 , v) = (n -2(k -1))d k m (n + 1). d(T ) ≥ 1 - 1 n d(T * n ) + 2 1 - 2(k -1) n d k m (n + 1)
Using (21), we derive:

d(T ) ≥ 1 - O(k) n 2 d k m (n + 1) + k-1 i=1 d k m (a i ) + k-1 i=1 d k m (b i ) + 1 - O(k) n opt(J k )
Using [START_REF] Schäffter | Scheduling with forbidden sets[END_REF], the previous inequality gives equation [START_REF] Serdyukov | An algorithm with an estimate for the traveling salesman problem of the maximum[END_REF].

This equation is valid for any k. Now, let us write this inequality for k = 1, • • • , K. Let us consider the two following cases :

1. If, for some k, d k m (a k )+d k m (b k ) ≤ 1 K d(T * n+1 ), then we get d(T ) ≥ 1 -O(k) n 1 -1 K d(T * n+1 ). Hence: d(T ) ≥ 1 - O(K) n 1 - 1 K d(T * n+1 ) Since K = √ n, we get d(T ) ≥ 1 -O 1 √ n d(T * n+1 ).
2. In the other case, for any k

, d k m (a k ) + d k m (b k ) ≥ 1 K d(T * n+1
). We now show that this is impossible. By making the sum, we get :

K k=1 d k m (a k ) + d k m (b k ) ≥ d(T * n+1 ) (22)
The only remaining thing is to upper bound this sum. Let us use (21) with k = 2 :

d(T * n ) = opt(J 1 ) ≥ 2(d 2 m (a 1 ) + d 2 m (b 1 )) + 1 - 2 n opt(J 2 )
If we apply the same inequality for opt(J 2 ), we get

d(T * n+1 ) ≥ 2(d 2 m (a 1 ) + d 2 m (b 1 )) + 2 1 - 2 n (d 3 m (a 2 ) + d 3 m (b 2 )) + 1 - 2 n 1 - 2 n -2 opt(J 3 )
Then, by recurrence:

d(T * n+1 ) ≥ 2 1 - 2 n -2K K K k=1 d k+1 m (a k ) + d k+1 m (b k ) + opt(J K+1 )
Now let us remark that :

(n -2k)d k+1 m (a k ) = (n -2(k -1))d k m (a k ) -d(a k , b k ) So, d k+1
d(T * n ) ≥ 2 1 - O(K) n d(T * n+1 )
This is impossible for n large enough. ⊓ ⊔

Proof of Proposition 2

Proof. We only present the proof for Best Insertion. Consider an optimum solution T * n+1 and let v i and v j be the neighbors of v n+1 in T * n+1 . Then d(T * n+1 ) ≤ d(T * n ) + d(v i , v n+1 ) + d(v j , v n+1 ) Now, consider the insertion of v n+1 between v i and a neighbor v i ′ in T * n .

d(T ) ≥ d(T * n ) + d(v i , v n+1 ) + d(v i ′ , v n+1 ) -d(v i , v i ′ )
Doing the same with a neighbor v j ′ of v j , and making the sum leads to :

d(T ) ≥ d(T * n ) + 1 2 (d(v i , v n+1 ) + d(v j , v n+1 ) -d(v i , v i ′ ) -d(v j , v j ′ ))
To conclude, we just have to notice that d(v i , v i ′ ) + d(v j , v j ′ ) ≤ d(T * n ). For the upper bound, consider the instance where all the distances in (K n , d) are 0, and consider an optimum solution (v 1 , v 2 , • • • , v n ). We assume that n is even. Then we set d(v i , v n+1 ) = 0 if i is even and 1 if i is odd. Then obviously Best Insertion gives a solution of value 1, while the optimum solution has value 2.

⊓ ⊔

Proof of Proposition 5

Proof. To get the approximation result, let v i and v j the nodes adjacent to v n+1 in T * n+1 . Consider now an optimum solution T * n , and let v i ′ and v i ′′ the two neighbors of v i and v j ′ and v j ′′ the two neighbors of v j in T * n .

T * n is (v i , v i ′ , • • • , v j ′ , v j , v j ′′ , • • • , v i ′′ ) (
with possibly i ′ = j ′ or i ′′ = j ′′ ). Note that if v i ′ or v i ′′ is v j , or if v j ′ or v j ′′ is v i , then deletion is optimum. Let P ′ be the sequence of nodes between v i ′ and v j ′ (eventually empty) and P ′′ the one between v i ′′ and v j ′′ .

Consider the following solutions on G: T 1 = (v n+1 , v i , v i ′ , P ′ , v j ′ , v i ′′ , P ′′ , v j ′′ , v j ), and the symmetrical T 2 = (v n+1 , v i , v i ′′ , P ′′ , v j ′′ , v i ′ , P ′ , v j ′ , v j ).

We get : 2d(T * n+1 ) ≥ 2d(v n+1,vi )+2d(v n+1,vj )+2d(T * n )-d(v i , v i ′ )-d(v i , v i ′′ )-d(v j , v j ′ )-d(v j , v j ′′ )

With deletion we get a solution T such that d(T ) ≥ d(T * n+1 ) -d(v n+1,vi )d(v n+1,vj ). Taking into account that d(v i , v i ′ )+d(v i , v i ′′ )+d(v j , v j ′ )+d(v j , v j ′′ ) ≤ d(T * n ), we get 2d(T ) ≥ d(T * n ). For the tightness of the bound, consider a graph on n + 1 nodes where d(v i , v j ) = M is i ≤ 2 and j ≥ 3 (or vice versa) and d(v i , v j ) = 1 otherwise. Then an optimum solution is (v 1 , v n+1 , v 2 , v n , v n-1 , • • • , v 3 , v 1 ), with value 4M + n -3. When we delete node v n+1 , we get a solution of value 2M + n -2. However, the value of an optimum solution on the final instance is 4M + n -4. The ratio can be arbitrary close to 1/2. ⊓ ⊔

Fig. 1 .

 1 Fig. 1. The graph Hi.

  m (a k ) ≥ d k m (a k ) -d(a k ,b k )n-2k , and hence:K k=1 d k+1 m (a k ) + d k+1 m (b k ) ≥ K k=1 d k m (a k ) + d k m (b k ) -2 K k=1 d(a k , b k ) n -2K But K k=1 d(a k , b k ) is the value of a matching, hence K k=1 d(a k , b k ) ≤ d(T * n+1). Using 22, we get:

  with nonnegative weights d on the edges, and T * n is an optimum solution of MinTSP (resp. MaxTSP) onI n = (K n , d), sub-instance of I n+k induced by the nodes {v 1 , • • • , v n }.Question : find a shortest (resp. longest) tour for the whole instance I n+k .Definition 2 (MinTSP-k, MaxTSP-k). We are given an instance (I n+k , T * n+k ) whereI n+k = (K n+k , d), K n+k is a complete graph on n+k nodes {v 1 , • • • , v n+k },with nonnegative weights d on the edges, and T * n+k is an optimum solution of MinTSP (resp. MaxTSP) on I n+k .

Question : find an shortest (resp. longest) tour on

  It is interesting to note that the behavior of Best and Longest Insertion are quite different for MaxTSP+ since Longest Insertion is only a 2/3-approximation, even asymptotically (see appendix). For MaxTSP+, in the metric case, Longest Insertion gives a 2/3-approximation, and this bound is tight (even if the graph has an arbitrary large number of nodes). In the metric case, Best Insertion is asymptotically optimum. More precisely, if the graph has n nodes, then Best Insertion is (1 -O(1/ Sketch).(see appendix for a complete proof) Let T * n be an optimum solution on the initial instance I n , T * n+1 an optimum solution on the final instance I n+1 , and T the solution obtained by applying Best Insertion on T * n

	Proposition 1. Theorem 4. √ n))-
	approximate.
	Proof (

Appendix

Proof of Lemma 1:

Proof. We reduce the usual s, t-hamiltonian path problem, known to be NPcomplete in general graphs of maximum degree 3 ([7]), to SHP a,b,s,t .

Let G = [V, E] be a graph of maximum degree 3 with node set V = {v 1 , . . . , v n }. We construct the bipartite graph H = [V ′ , E ′ ] containing n copies H 1 , . . . , H n of the graph depicted in Figure 1.


Federico Della Croce
email: federico.dellacroce@polito.it

Bruno Escoffier
email: escoffier@lamsade.dauphine.fr

Vangelis Th

Paschos
email: paschos@lamsade.dauphine.fr

Improved worst-case complexity for the min 3-set covering problem *

Keywords: Worst-case complexity, Exact algorithm, min set covering

We consider min set covering when the subsets are constrained to have maximum cardinality three. We propose an exact algorithm whose worst case complexity is bounded above by O * (1.3957 n ). This is an improvement, based on a refined analysis, of a former result (O * (1.4492 n )) by F.

In min set covering, we are given a universe U of elements and a collection S of (nonempty) subsets of U . The aim is to determine a minimum cardinality sub-collection S ′ ⊆ S which covers U , i.e., ∪ S∈S ′ S = U (we assume that S covers U ). The frequency f i of u i ∈ U is the number of subsets S j ∈ S in which u i is contained. The cardinality d j of S j ∈ S is the number of elements u i ∈ U that S j contains. We say that S j hits S k if both S j and S k contain an element u i and that S j double-hits S k if both S j and S k contain at least two elements u i , u l . Finally, we denote by n the size (cardinality) of S and by m the size of U . In what follows, we restrict ourselves to min set covering-instances such that: 1. no element u i ∈ U has frequency f i = 1; 2. no set S i ∈ S is a subset of another set S j ∈ S.

3. no pair of elements u i , u j exists such that every subset S i ∈ S containing u i contains also u j . Indeed, if item 1 is not verified, then the set containing u i belongs to any feasible cover of U . On the other hand, if item 2 is not verified, then S i can be replaced by S j in any solution containing S i and the resulting cover will not be worse than the one containing S i . Finally, if item 3 is not verified, then element u j can be ignored as any sub-collection S ′ covering u i will necessarily cover also u j . So, for any instance of min set covering, a preprocessing of data, obviously performed in polynomial time, leads to instances where all items 1, 2 and 3 are verified.

Let T (•) be a super-polynomial and p(•) be a polynomial, both on integers. In what follows, using notations in [START_REF] Woeginger | Exact algorithms for NP-hard problems: a survey[END_REF], for an integer n, we express running-time bounds of the form p(n).T (n) as O * (T (n)), the asterisk meaning that we ignore polynomial factors. We denote by T (n) the worst case time required to exactly solve the min set covering problem with n subsets. We recall (see, for instance, [START_REF] Eppstein | Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction[END_REF]) that, if it is possible to bound above T (n) by a recurrence expression of the type T (n)

T (n -r i ) + O(p(n)), we have T (n) = O * (α(r 1 , r 2 , . . .) n ) where α(r 1 , r 2 , . . .) is the largest zero of the function f (x) = 1 -x -r i .
There exist to our knowledge few results on worst-case complexity of exact algorithms for min set covering or for cardinality-constrained versions of it. Let us note that an exhaustive algorithm computes any solution for min set covering in O(2 n ). For min set covering the most recent non-trivial result is the one of [START_REF] Fomin | Measure and conquer: domination -a case study[END_REF] (that has improved the result of [START_REF] Grandoni | A note on the complexity of minimum dominating set[END_REF]) deriving a bound (requiring exponential space) of O * (1.2301 (m+n) ). consider here, the most notorious cardinality-constrained version of min set covering, the min 3-set covering, namely, min set covering where d j 3 for all S j ∈ S (notice that the bound of [START_REF] Fomin | Measure and conquer: domination -a case study[END_REF], for the case where

f i = 2, u i ∈ U , and d j = 3, for any S j ∈ S corresponds to O * (1.2301 (5n/2) ) ≈ O * (1.6782 n )).
It is well known that min 3-set covering is NP-hard, while min 2-set covering (where any set has cardinality at most 2) is polynomially solvable by matching techniques ( [START_REF] Berge | Graphs and hypergraphs[END_REF][START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF]).

Our purpose is to devise an exact (optimal) algorithm with provably improved worst-case complexity for min 3-set covering. We propose a search tree-based algorithm with running time O * (1.3957 n ). This result, largely inspired by the one of [START_REF] Della Croce | Computing optimal solutions for the min 3-set covering problem[END_REF], further improves it by reducing the complexity of the tree-based algorithm from O * (1.4492 n ) down to O * (1.3957 n ). This outcome is due to a different complexity analysis of the algorithm by the introduction of a kind of weights on the fixed sets. This technique seems to be quite close to the one very recently introduced in [START_REF] Fomin | Measure and conquer: domination -a case study[END_REF].

The following straightforward lemma holds, inducing some useful domination conditions for the solutions of min set covering. Lemma 1. There exists at least one optimal solution of min set covering where:

1. for any subset S j with d j = 2 containing elements u i , u p , if S j is included in S ′ , then all subsets S k hitting S j are excluded from S ′ ; 2. for any subset S j with d j = 3 containing elements u i , u p , u q , where S j double-hits another subset S k with d k = 3 on u i and u p , if S j is included in S ′ then S k must be excluded from S ′ and viceversa;

3. for any subset S j with d j = 3 containing elements u i , u p , u q , if S j is included in S ′ , then either all subsets S k hitting S j on element u i are excluded from S ′ , or all subsets S k hitting S j on elements u p and u q are excluded from S ′ .

Proof. We only prove item 1, items 2 and 3 being proved by the same kind of analysis. Assume, without loss of generality, that S j hits S k on u i and S l on u p . Suppose by contradiction that the optimal solution S ′ includes S j and S k . Then, it cannot include no more S l , or else, it would not be optimal as a better cover would be obtained by excluding S j from S ′ . On the other hand, suppose that S ′ includes S j , S k but does not include S l . Then, an equivalent optimal solution can be derived by swapping S j with S l .

In what follows, we consider the following counting. When we fix the status of a set of size 3, then our benefit is 1. When we do not fix a set of size 3 but cover one element of this set (hence this set will have size 2 is the remaining instance), we consider that our benefit is α 1. Obviously, when a set of size 2 is fixed, we can only consider that (in the worst case) our benefit is 1α. Hence, in some cases, the benefit is increasing with α while, in other cases, it is decreasing. An optimal value for α, following our analysis, is α = 0.297.

The rest of the paper is devoted to the proof of the following result.

Theorem 1. min 3-set covering can be optimally solved within time O * (1.396 n ).

The algorithm either reduces the min 3-set covering instance according to assumptions 1, 2 and 3 on the form of the instance (by detecting a subset S j to be immediately included in (excluded from) S ′ or an element u i to be ignored (correspondingly reducing the size of several subsets)), or applies a branching on subset S j , where the following exhaustive relevant branching cases may occur.

1. d j = 2: then no double-hitting occurs to S j or else, due to the preprocessing step of the algorithm, S j can be excluded from S ′ without branching. The following subcases occur.

(a) S j contains elements u i , u k with f i = f k = 2 where S j hits S l on u i and S m on u k . Due to Lemma 1, if S j is included in S ′ , then both S l and S m must be excluded from S ′ ; alternatively, S j is excluded from S ′ and, correspondingly, both S l and S m must be included in S ′ to cover elements u i , u k . For the analysis, consider the two following cases.

i.

d l = 3, or d m = 3, say d l = 3.
Then, in both cases (including or excluding S j ) we fix 3 -2α (1 for S l , (at least) 1α for S j and S m ). ii. d l = d m = 2, S l contains u i and u l and S m contains u k and u m , (with u l = u m , otherwise no need to branch). By including S j we fix 3(1α). Otherwise, u l is contained in S p and u m in S q . If S p = S q , then we fix at least 3(1-α)+2α = 3-α. Indeed, we fix 1α for any of the sets S j , S l , S m ; by covering u m , we fix α (resp., 1α α) if d p = 3 (resp., if d p = 2, since we can exclude S p ), and the same holds for covering u k . Note that this is still valid if S p = S q , since in this case we can exclude this set, which gives at least 1α 2α.

In case 1(a)i, we have

T (n) 2T (n -3 + 2α) + O(p(n)).
This results in a timecomplexity of O * (1.334 n ). In case 1(a)ii, we have

T (n) T (n -3 + 3α) + T (n -3 + α) + O(p(n)).
This results in a time-complexity of O * (1.336 n ).

(b) S j contains elements u i , u k with f i = 2 and f k 3, where S j hits S l on u i and S m , S p on u k . Due to Lemma 1, if S j is included in S ′ , then S l , S m , S p must be excluded from S ′ ; alternatively, S j is excluded from S ′ and, correspondingly, S l must be included in S ′ to cover element u i . For the analysis, consider the two following cases.

i. d l = 2, i.e., S l contains u i , u l ; then, f l 3 (or else we are in case 1a). Then, by including S j , we fix 4(1α) ((1α) for any of the sets S j , S l , S m , S p ); by excluding S j , we fix 2(1α) + 2α = 2 ((1α) for any of the sets S j , S l , and (at least) α for each set containing u l ). ii. If d l 3, i.e., S l contains at least u i , u l , u m , then by including S j , we fix 3(1-α)+1

(since now fixing S l gives benefit 1); by excluding S j , we fix (1α) + 1 + 2α = 2 + α (α from covering u l , and α from covering u m , with the same reasoning as in case 1(a)ii).

The worst case is 1(b)i where we get T (n)

T (n -2) + T (n -4 + 4α) + O(p(n)), resulting in a time-complexity of O * (1.338 n ).
(c) S j contains elements u i , u k with f i = 3 and f k 3 where S j hits S l , S m on u i and (at least) S p , S q on u k . Note that we can suppose that S j hits at least one set of size 3. Due to Lemma 1, if S j is included in S ′ , then S l , S m , S p , S q must be excluded from S ′ ; alternatively, S j is excluded from S ′ . For the analysis, consider the three following cases.

i. If d l = d m = d p = d q = 3, then we fix either 5α, or 1α.

Putting things together, the global worst case complexity is O * (1.3957 n ) and the proof of the theorem is complete. As a last word, let us note that a straightforward (improvable) analysis along the lines of Theorem 1, leads to an O * (1.1679 n ) time bound for minimum vertex covering in graphs of maximum size 3. Such a bound is the best-known dealing with search tree-based algorithms and is only dominated by the bounds in [START_REF] Beigel | Finding maximum independent sets in sparse and general graphs[END_REF][START_REF] Chen | Improvement on vertex cover for low-degree graphs[END_REF], (O * (1.1252 n ) and O * (1.152 n ), respectively) that are not based upon such algorithms. Note also, dealing with minimum dominating set in graphs of maximum size 3, analysis along the same lines reaches O * (1.344 n ), which is always the bestknown search-tree complexity.

Part of this research has been performed while the first author was in visit at the LAMSADE on a research position funded by the CNRS

ii. If d l = 2 or d m = 2, say d l = 2, then we fix either 5 -4α, or 1α. But in the case where we exclude S j from S ′ , then S l has size 2 and contains u i , whose frequency is now 2. Hence, we are either in case 1a or in case 1b. In the worst case, the branching gives (with case 1(b)i) 5 -4α, 5(1α) and 3α. iii. Finally, if d l = d m = 3, then we can suppose that f k 4 (otherwise we are either in case 1(c)i or in case 1(c)ii). In this case, by including S j we fix 2 + 4(1α) and by excluding S j we fix 1α.

In case 1(c)i, we get T (n)

(d) S j contains elements u i , u k with f i 4 and f k 4 where S j hits S l , S m , S p on u i and S q , S r , S s on u k . Note that we can suppose that S j hits at least one set of size 3. Due to Lemma 1, if S j is included in S ′ , then S l , S m , S p , S q , S r , S s must be excluded from S ′ alternatively, S j is excluded from S ′ . Then, we fix either 7 -6α or 1α getting T (n) T (n-1+α)+T (n-7+6α)+O(p(n)), resulting so in a time-complexity of O * (1.366 n ).

2. d j = 3 (that is, there does not exist S k ∈ S such that d k = 2) and there is at least one element u i with f i = 2. Then, S j contains u i , u j , u k , and S k contains u i , u l , u m (notice that no double crossing can occur between S j and S k due to the preprocessing step of the algorithm). Then, either we include S j , and we fix 1 + 3α new sets, or we exclude S j , and we have to include S k fixing so 2 + 2α new sets. In this case, we get

This results in a time-complexity of O * (1.366 n ).

3. d j = 3, all elements have a frequency at least 3, with S j double-hitting one or more subsets.

The following exhaustive subcases may occur.

(a) S j double-hits at least three subsets S k , S l , S m . Due to Lemma 1, if S j is included in S ′ then S k , S l , S m must be excluded from S ′ ; alternatively, S j is excluded from S ′ . This can be seen as a binary branching where either one subset (S j ) is fixed, or four subsets (S j , S k , S l , S m ) are fixed and hence,

This results in a time-complexity of O * (1.3803 n ).

(b) S j double-hits two subsets S k , S l . Note that the double-hit elements must be contained by another set. Note also that (at least) one element, say u i , is in S j , S k and S l . Consider the two following cases.

i. If f i 4, then either we include S j and then, by Lemma 1, we can exclude S k and S l , or we exclude S j . Then, either we fix 3 + 3α (3 for S j , S k , S l , and 3α since u i , u j and u k belong to at least one other set) or 1.

ii. If f i = 3, then we must include at least one set among S j , S k , S l , but we can suppose that we do not include two such sets. In other words, we have a branching on the three following choices:

• taking S j (and not S k , S l ),

• taking S k (and not S j , S l ),

• taking S l (and not S j , S k ). In any case, we fix 3 + 2α (2α since each element has a frequency at least 3)

In the first case, T (n)

This results in a time-complexity of O * (1.388 n ). In the second case, T (n) 3T (n -3 -2α) + O(p(n)), and this results in a time-complexity of O * (1.358 n ).

(c) S j contains elements u i , u k , u l and double-hits one subset S k on elements u i , u k . The following exhaustive subcases must be considered.

i. f i = 3, f k 3, f l 3, with u i contained by S j , S k , S m , u k contained at least by S j , S k , S p and u l contained at least by S j , S q , S r . A composite branching can be devised.

• Suppose that S j is included in S ′ and then S k is excluded from S ′ . In this case, we 2 + 4α (α from reduction of the sizes of S m , S p , S q , S r ). • Suppose that S j is excluded from S ′ and S k is included in S ′ . In this case, we fix 2 + 4α (since no other double hit occurs on S k ). • Suppose finally that S j and S k are excluded from S ′ . In this case, we have to include S m in S ′ . Since d m = 3, all elements have frequency at least 3, and at most one double crossing occurs on S m ; we can see that S m hits at least three new sets. Hence, we fix 3 + 3α. ii. f i 4, f k 4, f l 3, with u i contained at least by S j , S k , S m , S p , u k at least by S j , S k , S q , S r and u l contained at least by S j , S u , S v . Either we include S j in S ′ , and then we can exclude S k from S ′ and fix 2 + 6α, or we exclude S j and fix 1.

In case 3(c)i, we get

This results in a time-complexity of O * (1.3957 n ).

4. d j = 3 and no double-hitting occurs to S j (nor to any other subset) that contains elements u i , u k , u l . The following subcases occur.

(a) f i = 3, f k 3, f l 3 with u i contained by S j , S k , S l , u k contained by S j , S m , S p and u l contained at least by S j , S q , S r . A composite branching can be devised:

• if S j is included in S ′ , then we fix 1 + 6α new sets;

• if S j is excluded from S ′ and S k is included in S ′ then there exist at least five other subsets hitting S k and hence we fix 2 + 5α; • finally, if S j , S k are excluded from S ′ , then we have to include S l in S ′ (in order to cover u i ); there exist at least four other subsets hitting S l and hence we fix 3 + 4α.

u k is contained by S j , S p , S q , S r and u l is contained at least by S j , S t , S u , S v . A composite branching on S j can be devised:

• if S j is excluded from S ′ , then we fix 1;

• if S j is included in S ′ , then S k , S l , S m are excluded from S ′ ; in this case we fix 4 + 6α; • finally, if S j is included in S ′ , then S p , S q , S r , S t , S u , S w are excluded from S ′ ; in this case we fix 7 + 3α.

Hence, T (n) T (n -1) + T (n -4 -6α) + T (n -7 -3α) + O(p(n)). This results in a time-complexity of O * (1.355 n ).


Iza Marfisi-Schottman

Sébastien George

SUPPORTING TEACHERS TO DESIGN AND USE MOBILE COLLABORATIVE LEARNING GAMES

Keywords: Mobile Learning, Learning Games, Collaborative Learning, situated Learning, Game mechanics, adaptation 1. COLLABORATE

Mobile Collaborative Learning Games combine all the ingredients necessary to attract students' attention and engage them in learning activities. However, designing a coherent scenario that combines mobility, game mechanics and collaborative learning is quite a challenge. In this article, we take the first step by proposing several game patterns that naturally integrate these mechanics in order to support educational goals. We also discuss ways to support teachers design these applications and adapt them to their course material and specific learning situations. Finally, we identify the technical challenges linked to the deployment of these applications such as connectivity between mobile devices, geolocation, real time adaptation of scenarios by teachers and the use of data collected on the field as course material.

example, the MARL simulator [START_REF] Jayfus | Extending the Serious Game Boundary: Virtual Instructors in Mobile Mixed Reality Learning Games[END_REF] uses augmented reality to teach professional skills and psychomotor tasks on real car engines. Finally, mobility can be useful to explain a concept with live simulation. The Disease Simulation [START_REF] Colella | Participatory simulations: building collaborative understanding through immersive dynamic modeling[END_REF], for instance, was designed to teach children how a virus spreads. The participants wear digital tags that indicate if they are sick or not and, the same way a real virus spreads, the virtual illness is propagated when the children get close to one another.

Combining mechanics

While collaboration, game mechanics and mobility have proven to enhance learning on their own, we believe that their combination would be even more powerful because of the way they enhance and facilitate the use of each other. Even though a couple of researchers have successfully combined these mechanics, there is no study that identifies what makes this specific trio particularly powerful. In the next paragraph, we therefore identify and analyze the synergies between collaboration, game and mobility, represented as dotted arrows in Figure 1. Note that, on the same figure, the positive impacts of collaboration, game and mobility on learning, described in the first section of this article, are represented by full arrows.

Collaboration and Game

Setting up collaborative learning activities, where all the members of a group participate equally, is very challenging. [START_REF] Gómez | Co-located single display collaborative learning for early childhood education[END_REF], argue that this is possible by designing the activities so that each of the students has a specific interdependent task he/she needs to achieve. In order to encourage the students to do their one tasks, they designed a game where three students each hold a mouse, connected to the same screen and, in order to win the game, the team needs to complete various tasks that can only be done with one specific mouse. In other words, the students are given different tools (in this case, a mouse), which allow them to complete complementary tasks, and therefore collaboratively achieve a common goal. We believe game mechanics provide a natural way of setting up such mechanics. Indeed, like in Environmental Detective [START_REF] Klopfer | Environmental Detective, the development of an augmented reality platform for environmental simulations[END_REF], the game can be designed so players are given complementary roles (e.g. manufacturing company worker, environmental activist) with specific goals, thus forcing each learner to speak for him/herself. The game can also push this principal further by giving specific tools and powers to these roles (e.g. sorcerer, troll, chemist) so that the students are the only ones capable of doing certain tasks.

On the opposite, the use of collaboration is also recognized as one of the mechanisms that enhances games [START_REF] Björk | Patterns In Game Design[END_REF]. This is due to the social interactions and the extra challenge of team decision making.

Game and Mobility

Mobility offers new possibilities for enriching games and enhancing the users experience by taking advantage of real objects (e.g. plants, buildings, animals) in real contexts (e.g. archeological or geological site, factory, nature) [START_REF] Daniel | Getting Into Position: Serious Gaming in Geomatics[END_REF]. Several studies have also shown that physically excitement caused by walking, running or jumping during the game increases players engagement [START_REF] Bianchi-Berthouze | Understanding the Role of Body Movement in Player Engagement[END_REF]. Finally, smartphone functionalities such as GPS, accelerometer and other sensors that collect feedback can provide valuable information in order to improve engagement in the game. For example, if the player has been standing in the same area for a long time or has been going round in circles, the game could automatically provide some hint on what to do next.

On the opposite, game rewards such as extra points or unlocking the next part of the story, can also help motivate the learners to physically move to the next location. This is for example the case of Rewild1 , an adventure games that motivates non-hikers to discover the beauty of nature.

Mobility and Collaboration

If well designed, collaborative activities can greatly enhancement the concept of mobility. Indeed, by forcing the team members to organize and synchronize their movements in order to cover the whole map or to be at a specific location at a given time, collaboration can give a new gaming dimension to mobility.

On the opposite, mobility can lead to situations where the team members are physically dispersed and don't always have the means to communicate. These situations make collaborative activities much more challenging. In addition, when working in collaboration, it often happens that the team members don't progress at the same speed. For instance, some of them might need to come back on certain activities or read the instructions again. With the use of personal mobile interfaces, each student can navigate freely in the activities and submit their personal work when they feel ready [START_REF] George | Introducing Mobility in Serious Games: Enhancing Situated and Collaborative Learning[END_REF].

As we have seen, several learning applications already take advantage of the synergies between collaboration, game mechanics and mobility. However, their design remains experimental; without any methods to make sure these mechanics are used to their full potential. In addition MCLG (Mobile Collaborative Learning Game) design is far from being trivial. Indeed, not only does it combine the challenges identified by researchers in Collaborative Learning, Learning Games and Mobile Learning such as designing coherent scenarios, reducing production cost and helping teachers and students adopt the applications but it also raises extra challenges resulting from the difficulty of combining these three mechanics. Given the power of this trio and the high demand for applications that motivate and engage students, we believe it is important to assist their design and use. In this article, we first put forward several solutions for designing coherent scenarios that integrate collaboration, game mechanics and mobility in such a way to create the desired synergy and facilitate the learning process. Then we discuss how to support teachers to use MCLGs and adapt them to their course material and their specific learning situations.

DESIGNING LEARNING SCENARIOS

As we have shown, MCLGs have all the necessary ingredients to engage students in learning activities. However, it takes more than just knowing the right ingredients to make a good cake. Indeed, the ingredients need to be carefully selected, dosed, mixed and cooked in a certain way in order to create the final enhanced product, that is much more than just an addition of all the ingredients. We believe designing MCLGs raises the same challenge: selecting, dosing and combining learning activities, collaboration, game mechanics and mobility in order to create synergies and hence, maximize educational value.

Because there are no recipes or authoring tools that provide guidance for designing MCLGs yet, we take the first step by proposing three game patterns that naturally integrate these mechanics and support specific educational goals. Bear in mind that this is just the first step, as we would also need to provide teachers with guidance and more examples in order to help them choose and use the right patterns.

Live action role-playing game

LARPs (Live Action Role-Playing games) are built around role playing activities guided by rules. Players usually have full control over decisions made by their character and the game scenario is completely dependent on their actions. LARPs are usually guided by a game master who facilitates the game flow, administrates the game rules and keeps score [START_REF] Tychsen | Live Action Role-Playing Games Control, Communication, Storytelling, and MMORPG Similarities[END_REF]. In terms of education, LARPs seem ideal for practicing social skills or understanding complex subjects that don't have a given solution and involving several actors. In addition, the role of the game master is perfect for teachers because it allows them to observe the learners and adapt the game scenario accordingly. A variation of this game type is to strip the roles down to the minimum and focus on the rules that condition the interactions between the players. This can be used to create a participatory simulation of a specific mechanism such as the virus epidemic in the game Disease Simulation, described in the first section of this article.

Similarly to game design pattern libraries [START_REF] Björk | Patterns In Game Design[END_REF], we depict each MCLG pattern with a specific structure and an example. These examples are inspired by real games, designed and used by teachers at different levels of education.

Example 1: Pattern LARP -Fast way construction

Educational goal: Understand the mechanisms of democracy and practice how to defend an opinion by collecting data and presenting it orally. Game: The town mayor has the project of building a fast way thought a section of his city. However, he would like to debate this project with the citizens before making a decision. Mobility: With a map of the construction plan for the road, the players need to investigate on the field to find elements that are in favor or against the construction of the road. Regularly, the players are summoned to a general town meeting to present and discuss their point of views on the road project. Collaboration: At the beginning of the game, the players are assigned to complementary roles so that they represent the town population:

-The mayor would like his town to grow but doesn't want to go against the general opinion -Citizens who live next to the construction area and would be bothered by the noise -Citizens who would be able to reduce their transportation time by taking the fast way -Local store managers who would increase their sales if the fast way was built -Environmental activists who want to protect the bird sanctuary, the road will go through -Owners of construction companies who would be able to hire people to work on the road -Two journalists, one in favor and one against the road construction, who need to conduct surveys on the general opinion and keep the population informed of the local news Note that the scoring mechanism is different for each role and is designed so that the players will need to negotiate and come up with a solution that suits all the participants. However, the teacher that used this game noticed that, even though the scoring mechanism seems to motivate the students in the beginning, they often forget it completely by the end of the game.

Mystery game

The scenario of a mystery game is built around a central mystery that players need to solve by collecting clues, analyzing them and deducting possible solutions. This model is very similar to the case-based teaching method that consists in presenting learners with a problem, inspired by a real situation, and putting them in the position of decision makers. We believe this game model is therefore perfectly adapted to make students practice the use of theoretical knowledge through collaborative resolution of complex cases. Educational goal: Practice how to use decision making tools on a real complex problem. Game: The students are hired by a company to understand why it has been losing so much money lately. They have a limited time to identify the problem and find solutions. Mobility: The players need to physically go to various rooms of a building in order to investigate. They collect information, such as videos of fictional employees being interviewed or important documents, by scanning the QR codes in each room. The teacher regularly gathers all the students to discuss their finding and reflect on the decision making tools they can use to help them. Collaboration: In order to finish the game in time, the players, in groups of three, needs to organize and divide their tasks. For example, in the beginning of the scenario, each player decides which rooms he/she is going to visit in order to collect information and, in the next phase, when they have several hypotheses on what is causing the money los, they also need to divide the work for further investigations.

Treasure hunt

A treasure hunt is a game in which players attempt to find hidden items with a series of clues. Because this type of game pushes players to explore the environment and get familiar with it, we think it is very well suited to teach about the characteristics of real items, locations and environments.

Example 3: Pattern Treasure hunt -Bacchus' party

Educational goal: Learn about life in Ancient Rome and the end of Pompeii. Game: The players are hired by Bacchus to organize a party in his honor. They are given a list of items that they need to find (beverage, food, gests and animations) and a certain amount of gold coins. However, the amount of money is not sufficient, so the players will have to make a decision: only buy what they can, and therefore score very low on Bacchus' happiness scale, or steel! If they steel, the volcano will start showing signs or eruption and the virtual inhabitants of Pompeii will tell them that it is God who is angry at the sinful population. At the end of the game, whatever the decisions made by the players, the volcano erupts anyway, just like it really happened. If they stool, God starts the eruption and if they didn't steel or didn't collect all the items in time, and therefore didn't fulfill Bacchus' expectations, his fury triggers the eruption. Mobility: The students have a few hours to physically go around the ruins of Pompeii and find the items they need in the real locations where the shops where. To find the gests and animations, they have the choice between the house of poets and dancers, the gladiator barracks and several villas of noble families. Collaboration: In order to collect all the items in time, the players need to divide their tasks. When they realize the shortage of money, they will also need to contact each other and decide what strategy to adopt.

These three design patterns are first steps toward designing motivating and educationally rich MCLGs. However, this is far from being sufficient to get teachers to use MCLGs in their class. Indeed, not only do teachers need to feel at ease installing and using these games but their content and shape also need to be compatible with their educational context (e.g. student's level, curriculum, number of students). In the next section, we discuss solutions to meet these expectations.

PLACING THE TEACHER IN THE CENTER

When considering the multitude of learning applications developed for research, it is surprising to see how few of them are actually used by teachers. This can party be explained by the obsolescence of hardware and software but it is mainly due to the fact that the educational content and the shape of the applications simply don't meet the teacher's needs. In some cases, especially for Learning Games, the applications are designed without the presence of teachers [START_REF] Ketam | Integrating Games into the Classroom: Towards New Teachership[END_REF]. In this case, they are quite unlikely to integrate the pedagogical structure that teachers need for their courses. In most cases though, learning applications are designed with the help of one teacher but they are therefore tailored for that specific teacher and one particular educational context. Because these applications leave very little room for adaptation, without any computer skills, they often cannot be used by other colleagues or even by the same teacher but with another class [START_REF] Marne | MoPPLiq: A Model for Pedagogical Adaptation of Serious Game Scenarios[END_REF]. This rigidity causes most applications to be put away and forgotten after just a few years. Another reason that can explain the fact that learning applications are rare in school is that they are often set up by professional computer scientist and, unless the teachers are very skilled with computers, it is highly improbable they will be able to set them up again if there is a technical problem or if the school is provided with new computers and mobile devices.

In order to get the maximum number of teachers to use MCLGs, we therefore believe it is necessary to place them in a central and active role during the design process and the use of these applications. In the next section, we provide leads on how to design tools to help teachers:

 design their own MCLGs and understand the mechanisms under the lid to adapt them  monitor the student's progression in the game and adjust the scenario in real time  easily deploy MCLGs on the available mobile devices and fully integrate them to their course

Design and Understand

Before using any kind of tool in class, teachers feel the need to test it and understand the way it works. This is a necessary step to decide if the tool corresponds to their needs and to plan how they want to use it with their students. This step is a big concern to teachers, especially when dealing with unknown game mechanics. Indeed, if it is not clearly stated, it is difficult to imagine how they can impact a course. The fear of not being able to control students when they are "frantically playing" is often enough to discourage teachers.

In order to design MCLGs that correspond to the teacher's needs, and help them understand the game mechanics, we believe it is indispensable to involve them in the design process as early as possible. In the field of Learning Games, this challenge has been answered with two different strategies. The first solution is to help teachers design games with the help of game designers. In order to help them understand each other and work in an efficient way, several authoring tools have been developed [START_REF] Marfisi-Schottman | Tools and Methods for Efficiently Designing Serious Games[END_REF]. This solution has the advantage of providing original game scenarios, custom-tailored to fit the teacher's needs however, as you can image, the services of a game expert and the development cost are not affordable by many schools. The second solution consists in providing teachers with premade game-shells in which they can add their educational content. These shells often come with more or less complex editors that allow teachers to generate their own functional applications for a very low cost, because they need little or no help from developers and graphic designers [START_REF] Thiagarajan | Design your own games and activities: Thiagi's templates for performance improvement[END_REF] [START_REF] Mehm | Authoring Environment for Story-based Digital Educational Games[END_REF][START_REF] Marfisi-Schottman | Building on the Case Teaching Method to Generate Learning Games Relevant to Numerous Educational Fields[END_REF].

Because one of our goals is to widen the use of MCLGs to all types of schools and levels of education, we believe that building on the second solution is the most promising. However, in our opinion, the existing authoring tools, such as eAdventure [START_REF] Moreno-Ger | Educational game design for online education[END_REF] and Storytec [START_REF] Mehm | Authoring Environment for Story-based Digital Educational Games[END_REF], are fare from answering the teacher's needs and there is still quite a few improvements to make. The most important drawback is the very limited selection of game-shells that exist. Providing game-shells that correspond to the MCLG patterns we proposed in the second section of this article would be a good start to address this issue. The existing editors also lack flexibility and it is very difficult for teachers to compose a scenario that fits exactly to their needs. Finally, we believe authoring tools also need to provide information on the game mechanics and the education situations that they create, in order to help teachers choose the right games and use them correctly.

Monitor and Adjust

When giving a course, teachers naturally adapt the content (e.g. formulation of sentences, order of exercises, adding questions) depending on the student's achievements and emotions (e.g. facial expressions). If we want teachers to feel at ease with MCLGs, they must also provide them with feedback on the student's actions and allow real-time control over the events.

For this purpose, [START_REF] Carron | Enhancement of Adaptation and Monitoring in Game-Based Learning Environments[END_REF] recommend using monitoring tools that enable teachers to view the progression of their students through the game. Because students might be running around in the fields when using MCLGs, these tools could also provide information on their physical and logical location. They could also show large grain information such as "student needs help" or "student is in advance" when certain patterns are identified in lower level data, collected from the GPS tracks, scoring and feedback.

We believe teachers should also be able to adjust MCLGs' scenarios when they identify a problem. These adjustments can be done for one student in particular (e.g. sending a hint or an extra quest) or for all the students by adapting the global scenario (e.g. stopping the game, deleting a part of the scenario). In any case, given the mobility of MCLGs, teachers should have the means of communicating with a particular student or with the entire group at the same time. The intervention of teachers is also a good way of making game scenarios more interesting and unpredictable. In Laboratorium of Epidemiologie [START_REF] Ney | Phone, email and video interactions with characters in an epidemiology game: towards authenticity[END_REF] for instance, the students are not aware that one of the important characters is piloted by the teacher. Not only does this allow the teacher to subtly adapt the level of difficulty to the student's profile but the students also seem to accept negative comments coming from the game characters much better than if they came directly from the teacher. In certain cases, it might also be interesting to let teachers pilot the whole scenario of events depending on the student's reactions. For instance, [START_REF] Ponder | Immersive VR decision training: telling interactive stories featuring advanced virtual human simulation technologies[END_REF] designed a simulator in which the students have to provide first aid care and, depending on the actions of the learner (e.g. moving the body, heart massage), the teacher triggers other events (e.g. person goes unconscious, starts bleeding). The idea is to adjust the scenario so that is pushes the student into a stressful state.

Deploy

The execution of MCLGs is a real challenge of its own. Indeed, these applications not only need to be functional on various mobile devices but the content collected during the field expedition must be easily transferable to desktop computers in order to be further analyzed and used as course material [START_REF] George | Introducing Mobility in Serious Games: Enhancing Situated and Collaborative Learning[END_REF]. Ideally, if the teachers use a LMS (Learning Management System), their student's achievements in the game should also be added into this system. We believe the new Tin Can API2 seems to fit the purpose but needs to be further tested. Indeed, this API allows collecting data about the wide range of experiences a person has from various inputs (e.g. LMS, mobile applications, social networks, Web activity).

In order to support collaborative scenarios and their real-time adaptation by teachers, MCLGs scenarios also need to be executed by a centralized game engine that orchestrates the activities depending on the learner's actions and roles. Such a flexible orchestration could, for example, be possible with IMS-LD3 modeling. Indeed this E-learning standard is recognized by course designers and executable by many online tools. However, it has been criticized for the difficulty of modeling collaborative activities and its level of abstraction too far from teachers' practices. One of the future research challenges is therefore to propose a model for designing MCLGs, that can be easily understood and manipulated by teachers, and that can also be transform into an executable IMS-LD model.

CONCLUSION

In this article, we discuss the way collaboration, game mechanics and mobility can engage students and enhance their learning process. We also show that, when these three mechanics are combined in a MCLG (Mobile Collaborative Learning Game), they create synergies and should therefore be even more effective. However, for the time being, there are no tools or methods to help teachers design and use MCLGs in class in such a way to obtain these synergies.

In order to address this issue, we first provide three game patterns that can be used as models for designing MCLGs: live action role-playing games, mystery games and treasure hunts. These patterns naturally create the synergies between collaboration, game mechanics and mobility and fit a large range of educational goals such as understanding complex mechanics, practicing professional skills in the real context and learning about situated objects and environments. We then put forward the challenge of making teachers use learning applications, such as MCLGs, in their class. We believe the best solution is to involve teachers as early as possible in the design process of MCLGs and also provide them with tools to monitor their student's actions and adapt the game scenario in real time. As a first step toward the technical deployment of MCLGs, we also identify the existing tools that could be put together in order to obtain a game engine capable of multi-platform execution, multi-role scenarios, real time scenario adaptation and exporting the data collected on the field to be used as course material.

Figure 1 :

 1 Figure 1: Positive interconnections between Collaboration, Game, Mobility and Learning

  These cases can cover a very large variety of educational domains: finding what pathology a patient is suffering from, understanding what broke a piece of machinery, finding the best solution for a divorce case (Marfisi-Schottman et al., 2013)… Example 2: Pattern Mystery game -Company investigation

http://www.rewild.fr

http://www.tincanapi.com/

http://www.imsglobal.org/learningdesign/index.html


Vincent Andrieu
email: vincent.andrieu@gmail.com

Laurent Praly
email: laurent.praly@mines-paristech.fr

† L Praly

Note on diffeomorphism extension for observer design

An often encountered way of designing an observer is to use coordinates different from the given ones (or the ones of interest). This is done via the construction of a diffeomorphism (maybe obtained following the extension of an injective immersion) and an extended vector field on which is designed the observer. The estimated state is then obtained by employing the left inverse of the diffeomorphism (which may be difficult to obtained). A possible solution to overcome this difficulty is to use a diffeomorphism extension. A first preliminary result is given in this note.

Introduction

Consider the system: ẋ = f (x) , y = h(x) ,

with x in A ⊂ R n is an open forward invariant set and y in R.

An often encountered way of designing an observer is to use coordinates different from the given ones (or the ones of interest). This is done via the construction of a diffeomorphism (maybe obtained following the extension of an injective immersion as in [START_REF] Andrieu | Dynamic extension without inversion for observers[END_REF]) τ * : A → R n and a (extended) vector field ϕ : R n × R → R n such that ξ = ϕ(ξ, y) , y = h(τ (ξ)) , ξ ∈ τ * (A) [START_REF] Gauthier | A simple observer for nonlinear systems, application to bioreactors[END_REF] is the image of the system (1) with the diffeomorphism τ * and such that the system ξ = ϕ( ξ, y) , defines an observer for the system (2). In other words, we have,

lim t→+∞ Ξ( ξ, ξ, t) -Ξ(ξ, t) = 0 , ∀(ξ, ξ) ∈ τ * (A) × R m
An observer for the system (1) is then defined as

x = τ ( ξ) , ξ = ϕ( ξ, y) , (3)
where τ is an inverse of τ * . A possible way to implement this observer is as follows (see for instance [START_REF] Gauthier | A simple observer for nonlinear systems, application to bioreactors[END_REF] and [START_REF] Andrieu | Dynamic extension without inversion for observers[END_REF])

ẋ = f (x) + ∂τ * ∂x (x) -1 [ϕ(τ * (x), y) -ϕ(τ * (x), h(x))]
But this expression makes sense only in the set in which ∂τ * ∂x (x) -1 is well defined, i.e. as long as its solutions x is in A. A possible solution to overcome this difficulty is to extend the diffeomorphism outside A. Indeed, if we construct a diffeomorphism τ * e : R n → R n such that for all x in A, we have τ * (x) = τ * e (x) then a possible implementation of the observer would simply be:

ẋ = f (x) + ∂τ * e ∂x (x) -1 [ϕ(τ * e (x), y) -ϕ(τ * e (x), h(x))]
In this note, based on [START_REF] Hirsch | Differential topology[END_REF] we investigate the possibility of extendeding a diffeomorphism.

Diffeomorphism extension

In the following, we denote by B R (0)) the open ball in R n which is centered at 0 and has radius R.

Proposition 1 (Extension of the diffeomorphism on a ball) Assume there exists a

C 2 function ψ : R n → R n such that ψ(0) = 0 and ψ : B R (0)) → ψ(B R (0)) ⊂ R n is a diffeo- morphism.
Then for any δ in (0, R), there exists a diffeomorphism ψ e : R n → R n such that ψ e (x) = ψ(x) for all x in the closure cl(B R-δ (0)).

Proof : Let δ in (0, R), we denote

T = R R -δ > 1 , R 2 = R R -δ R , R 1 = R -δ .
Note that we have

B T R 1 (0) = B R 2 (0) , B T R 2 (0) = B R (0) . Consider the function ϕ : B R 2 (0) × (-T, T ) → R n defined as ϕ(x, t) = ∂ψ ∂x (0) -1 ψ(xt) t for t = 0 , ϕ(x, 0) = x .
We study the properties of the function x → ϕ t (x) = ϕ(x, t) with t fixed in (-T, T ).

• Let x a and x b be in B R 2 (0) satisfying ϕ(x a , t) = ϕ(x b , t) .

If t = 0, this implies readily ψ(x a t) = ψ(x b t) .

Since the pair (x a t, x b t) is in B R (0) for all t in (-T, T ) and since the function ψ is injective on this set, we obtain x a = x b .

If t = 0, we get this last inequality directly. So we have established the injectivity of ϕ t on B R 2 (0) for all t in (-T, T ).

• we have

∂ϕ t ∂x (x) = ∂ψ ∂x (0) -1 ∂ψ ∂x (xt) for t = 0 ∂ϕ 0 ∂x (x) = Id and lim t→0 ∂ψ ∂x (0) -1 ∂ψ ∂x (xt) = Id Hence ϕ t is C 1 on B R 2 (0)
. Moreover, since by assumption the matrix ∂ψ ∂x (xt) is invertible for all t in (-T, T ) and

x in B R 2 (0). ϕ t is full rank on B R 2 (0).
We conclude that, for all t in (-T, T ), the function

x → ϕ t (x) ϕ(x, t) is a diffeomorphism from B R 2 (0) onto ϕ t (B R 2 (0)). Let ϕ -1 t denote its inverse map.
Similarly, let us study the properties of the function ρ defined as :

ρ(x, t) = 1 t 2 ∂ψ ∂x (xt)xt -ψ(xt) for t = 0 , ρ(x, 0) = 1 2 x ′ ∂ 2 ψ ∂x∂x (0) x
• The function ψ being C 2 , and satisfying ψ(0) = 0, we have

lim t→0 ψ(xt) -∂ψ ∂x (0)xt t 2 = 1 2 lim t→0 ∂ψ ∂x (xt)x -∂ψ ∂x (0)x t = 1 2 x ′ ∂ 2 ψ ∂x∂x (0) x
This implies that the function ρ is well defined and the function t → ρ(x, t) is continuous.

• We get ∂ρ ∂x (x, t) = ∂ 2 ψ ∂x∂x (xt)x ∀t ∈ (-T, T ) .
Since xt is in B R (0) for all t in (-T, T ) and x in B R 2 (0) and ψ is C 2 on R n , this implies that the function x → ρ(x, t) is Lispchitz on the closure B R 2 (0) uniformly in t in (-T, T ). Now we observe that we have

˙ ϕ(x, t) = ∂ϕ ∂t (x, t) = ∂ψ ∂x (0) -1 ρ(x, t) = ∂ψ ∂x (0) -1 ρ ϕ -1 t (ϕ(x, t)) , t
This motivates us for considering the time varying system

ż = ζ(z, t) = ∂ψ ∂x (0) -1 ρ ϕ -1 t (z), t (4)
is well defined on the open set

O = (z, t) : t ∈ (-T, T ) , z ∈ ϕ t (B R 2 (0))
where it is continuous and Lipschitz in z. It follows that t → ϕ(x, t) is the unique solution on (-T, T ) of this system which goes through x at t = 0. With Z(z, t) denoting a solution of (4), we have

Z(x, t) = ϕ(x, t) ∀(x, t) ∈ B R 2 (0) × (-T, T ) .
The above time varying system can be extended to R n × (-T, T ) as

ż = ζ e (z, t) =    0 if z / ∈ ϕ t (B R 2 (0)) , χ ϕ -1 t (z) ∂ψ ∂x (0) -1 ρ ϕ -1 t (z), t if z ∈ ϕ t (B R 2 (0)) , (5)
where χ : R n → R + is a C 1 function satisfying

χ(x) = 0 if x / ∈ B R 2 (0) , 1 if x ∈ B R 1 (0) .
This extended system is continuous on R n × (-T, T ) and Lipschitz in z. So it has well defined and unique solutions on (-T, T ) for any initial condition z in R n . We denote by Z e (z, t) such a solution going through z at time t = 0. From this definition and since 1 is in (0, T ), the function z → Z e (z, 1) is a diffeomorphism. Also if, for some τ ≥ 0, a solution Z ( z, t) of ( 4) is in ϕ t (B R 1 (0), for all t in [0, τ ], then t → Z e (z, t) is solution of (5) at least on [0, τ ]. But by definition, when x is in B R 1 , ϕ(x, t) is in ϕ t (B R 1 (0) for all t in (-T, T ). With uniquesness of solutions, this implies Z(x, 1) = ϕ(x, 1) ∀x ∈ B R 1 (0) .

We are now ready to define the extension ψ e as ψ e (x) = ∂ψ ∂x (0)Z(x, 1) .

Since ∂ψ ∂x (0) is an invertible matrix, it is a diffeomorphism on R n . Moreover we have

ψ e (x) = ∂ψ ∂x (0)ϕ(x, 1) = ψ(x) ∀x ∈ B R 1 (0) .

✷

Note that to realize the extended diffeomorphism we have to integrate the model (5) which depends on the inverse of the function ϕ t . Hence, we come back to our preliminary problem.

Note however that for all x in R n and t in [0, 1] such that Z e (x, t) is in ϕ t (B R 2 (0)), if we note v = ϕ -1 t (Z e (x, t)) we have,

∂ϕ t ∂t (v) + ∂ϕ t ∂x (v) = χ(v) ∂ψ ∂x (0) -1 ρ (v, t)
where by definition

∂ϕ t ∂t (v) = ∂ϕ ∂t (v, t) = ∂ψ ∂x (0) -1 ρ (v, t) .
Consequently, for all x in R n and t in [0, 1] such that Z e (x, t) is in ϕ t (B R 2 (0)), if we note v = ϕ -1 t (Z e (x, t)) we have, v = (χ(v) -1)

∂ϕ t ∂x (v) -1 ∂ϕ t ∂t (v)
Note however that this is still difficult to implement. Indeed, in this case, Z e (x, t) is solution to this time dynamical system:

ż = 0 , z / ∈ ϕ t (B R 2 ) z = ϕ t (v) , v = (χ(v) -1) ∂ϕt ∂x (v) -1 ∂ϕt ∂t (v) , z ∈ ϕ t (B R 2 )
However, if we have the property that, if t → ϕ t (B R 2 ) is a strictly decreasing set valued map.

Then this system can be implemented without inverting the function.