G Duvillié

M Bougeret
email: marin.bougeret@lirmm.fr

V Boudet

T Dokka
email: t.dokka@lancaster.ac.uk

R Giroudeau
email: rodolphe.giroudeau@lirmm.fr

On the complexity of Wafer-to-Wafer Integration

In this paper we consider the Wafer-to-Wafer Integration problem. A wafer is a p-dimensional binary vector. The input of this problem is described by m disjoints sets (called "lots"), where each set contains n wafers. The output of the problem is a set of n disjoint stacks, where a stack is a set of m wafers (one wafer from each lot). To each stack we associate a p-dimensional binary vector corresponding to the bit-wise AND operation of the wafers of the stack. The objective is to maximize the total number of "1" in the n stacks. We provide O(m 1-) and O(p 1-) non-approximability results even for n = 2, as well as a p r -approximation algorithm for any constant r. Finally, we show that the problem is FPT when parameterized by p, and we use this FPT algorithm to improve the running time of the p r -approximation algorithm.

Introduction

Problem definition

In this paper we consider Wafer-to-Wafer Integration problems. In these problems, we are given m disjoint sets V1 . . . V m , where each set V i contains n binary p-dimensional vectors. For any j ∈ [n]1 1 , and any i ∈ [m]1, we denote by v i j the j th vector of set V i , and for any k ∈ [p]1 we denote by v i j (k) ∈ {0, 1} the k th component of v i j . Let us now define the output. A stack s = (v s 1 , . . . , v s m ) is an m-tuple of vectors such that v s i ∈ V i , for any i ∈ [m]1. An output of the problem is a set S = {s1, . . . , sn} of n stacks such that for any i and j, vector v i j is contained exactly in one stack. An example of input and output is depicted in Figure 1.

These problems are motivated by an application in IC manufacturing in semiconductor industry, see [START_REF] Reda | Maximizing the functional yield of wafer-towafer 3-d integration[END_REF] for more details about this application. A wafer can be seen as a string of bad dies (0) and good dies [START_REF] Crescenzi | Structure in approximation classes[END_REF]. Integrating two wafers corresponds to superimposing the two corresponding strings. In this operation, a position in the merged string is only 'good' when the two corresponding dies are good, otherwise it is 'bad'. The objective of Wafer-to-Wafer Integration is to form n stacks, while maximizing the overall quality of the stacks (depending on the objective function).

Let us now define several objective functions, and the corresponding optimization problems. We consider the operator ∧ which maps two p-dimensional vectors to another one by performing the logical and operation on each component of entry vectors. More formally, given two p-dimensional vectors u and v, we define u∧v = (u(1)∧v [START_REF] Crescenzi | Structure in approximation classes[END_REF], u(2)∧v(2), . . . , u(p)∧v(p)). We associate to any stack s = (v s 1 , . . . , v s m ) a binary p-dimensional vector vs = m i=1 v s i . Then, the profit of a stack s is given by c(vs), where c(v) = p k=1 v(k). Roughly speaking, the profit of a stack is the number of good bits in the stack, where a good bit (in position k) survives iff all the vectors of the stack have a good bit in position k. We are now ready to define two following optimization problems:

Set of problems 1 max 1 and min 0 Input m sets of n binary p-dimensional vectors Output a set S of n disjoint stacks

Objective functions max 1: maximize f 1 (S) = n j=1 c(vs j ), the total number of good bits min 0: minimize f 0 (S) = np -n j=1 c(vs j ), the number of bad bits

Instance of these problems will be denoted by I[m, n, p]. The notation f (S) (instead of f 0(S ), f 1(S ), . . . ) will be used when the context is non ambiguous.

Related work

In this paper we consider results in the framework of approximation and fixed parameter tractability theory. We only briefly recall the definitions here and refer the reader to [START_REF] Niedermeier | Invitation to fixed-parameter algorithms[END_REF][START_REF] Williamson | The design of approximation algorithms[END_REF] for more information. For any ρ > 1, a ρ-approximation algorithm A (for a maximization problem) is such that for any instance I,

A(I) ≥ Opt(I) ρ
, where Opt(I) denotes the optimal value. The input of a parameterized (decision) problem Π is a couple (X, κ), where X ⊆ Σ * is a classical decision problem, and κ : Σ * -→ N is a parameterization. Deciding Π requires to determine for any instance I ∈ Σ * if I ∈ X. Finally, we say that an algorithm A decides Π in FPT time (or that Π is FPT parameterized by κ) iff there exists a computable function f and a constant c such that for any I, A(I) runs in

O(f (κ(I))|I| c ).
The max 1 problem was originally defined in [START_REF] Reda | Maximizing the functional yield of wafer-towafer 3-d integration[END_REF] as the "yield maximization problem in wafer-to-wafer 3-D integration technology". Authors of [START_REF] Reda | Maximizing the functional yield of wafer-towafer 3-d integration[END_REF] point out that "the classical NP-hard 3-D matching problem is reducible to the max 1 problem". However, they do not provide the reduction and they only conclude that max 1 is NP-hard without stating consequences on the approximability. They also notice that max 1 is polynomial for m = 2 (as it reduces to finding a maximum profit perfect matching in a bipartite graph, solved by Hungarian Method), and design the "iterative matching heuristic" (IMH) that computes a solution based on (2D) matchings.

In [START_REF] Dokka | Approximation algorithms for the wafer to wafer integration problem[END_REF] and [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF] we investigated the min 0 problem by providing a 4 3 -approximation algorithm for m = 3 and several f (m)-approximation algorithms for arbitrary m (and for a more general profit function c). Furthermore, we also noticed in [START_REF] Dokka | Approximation algorithms for the wafer to wafer integration problem[END_REF] that the natural ILP formulation implied that min 0 and max 1 are polynomial for fixed p. Concerning negative results, the implicit straightforward reduction from k-Dimensional Matching in [START_REF] Dokka | Approximation algorithms for the wafer to wafer integration problem[END_REF] and made explicit in Appendix A, shows that min 0 is NP-hard, and max 1 is O( m ln m ) non-approximable. The more complex reduction of [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF] shows that min 0 is APX-hard even for m = 3, and thus is very unlikely to admit a PTAS. Table 1. Overview of results on Wafer-to-Wafer Integration

Contributions

In this paper we mainly study the max 1 problem, with a particular focus on parameter p. We prove in Subsection 2.2 that even for n = 2, for any , there is no ρ(m, p)-approximation algorithm for max 1 such that ρ(x, x) = O(x 1-) unless P = NP (this implies in particular no O(p 1-) and no O(m 1-) ratios). These negative results show that the simple p-approximation presented in Section 3.1 is somehow the best ratio we can hope for. Nevertheless, looking for better positive results we focus on p r -approximation algorithm for any constant r. It turns out that any O(f (n, m, p)) exact algorithm for max 1 can be used to derive a p r -approximation in O(p × f (n, m, r)). This motivates our main result: determining the complexity of the max 1 problem when parameterized by p. The natural ILP in [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF] implied that max 1 (and min 0) is polynomial for fixed p. In Section 3.2, we improve this result by showing that max 1 (and min 0) are FPT parameterized by p.

Negative Results

In order to obtain negative results for max 1, let us first introduce two related problems defined in the table Set Roughly speaking, we will see that approximating max 1 is harder than approximating these two problems, and that these problems are themselves nonapproximable.

To show that approximability is preserved we will provide strict reductions [1] noted S-reductions. Indeed, if there is a strict reduction from Π1 to Π2, then any polynomial ρ-approximation for Π2 yields to a ρ-approximation for Π1. Notice that in the following we will rather provide reductions as defined in the following property.

Property 1 Let Π1 and Π2 be two maximization problems with their given objective functions m1 and m2. Let f be a polynomial function that given any instance x of Π1 associate an instance f (x) of Π2. Let g be a polynomial function that given any instance x of Π1, and feasible solution S2 of f (x), associates a feasible solution g(x, S2) of Π1. If f and g verify the two following conditions:

1. Opt(x) = Opt(f (x)) 2. m1(g(x, S2)) ≥ m2(f (x))
then (f, g) is a strict reduction.

Relation between max =0 , max max 1 and max 1

Observation 1 There exists a strict reduction from max max 1 to max 1.

Proof. Let us construct (f, g) as in Property 1. Consider an instance I [m , n , p ] of max max 1. We construct an instance I[m, n, p] of max 1 as follows: we set

p = p , n = n , m = m + 1. The m sets of I [m , n , p ] remain unchanged in I[m, n, p]: ∀i ∈ [m ]1, V i = V i
and the last set V m +1 contains (n -1) "zero vectors" (i.e. vectors having only 0) and one "one vector" (i.e. vector having only 1).

Informally, the set V m +1 of I behaves like a selecting mask: since all stacks except one are turned into zero stacks when assigning the vectors of last set, the unique "one vector" of set V m +1 must be assigned to the best stack, and maximizing the sum of the stacks is equivalent to maximizing the best stack.

More precisely, it is straightforward to see that the following statement is true: ∀x, ∃ solution S of max max 1 of value fmax 1 (S ) = x ⇔ ∃ solution S of max 1 of value f 1(S ) = x. Thus, we get Optmax max 1(I ) = Optmax 1(I ). As the previous reduction is polynomial, and a solution of I can be deduced from a solution of I in polynomial time, we get the desired result.

Observation 2 There exists a strict reduction from max =0 to max 1.

We refer the reader to Appendix A for the reduction proving this lemma. According to Observations 1 and 2, any non-approximability result for max =0 or max max 1 will transfer to max 1. This motivates the next section.

Hardness of max =0 and max max 1

The reduction from k-Dimensional Matching (kDM) provided in [START_REF] Dokka | Approximation algorithms for the wafer to wafer integration problem[END_REF] can be adapted to max 1 instead of min 0 as shown in Appendix A Unlike the case of min 0, the reduction preserves approximability:

Theorem 1 (implicit in [START_REF] Dokka | Approximation algorithms for the wafer to wafer integration problem[END_REF]). There is a strict reduction from kDM to max =0.

As it is NP-hard to approximate kDM to a factor O( k ln(k) ) [START_REF] Hazan | On the complexity of approximating kdimensional matching[END_REF], we get the following corollary:

Corollary 1. It is NP-hard to approximate max =0 within a factor O( m ln(m) ).
We can also notice that any m r -approximation ratio (for a constant r ≥ 3) for max =0 or max 1 would improve the currently best known ratio for kDM set to Proof. Let us construct (f, g) as in Property 1. Let us consider an instance G = (V, E) of the Maximum Clique Problem. The corresponding instance of max max 1 is constructed as follows. We consider m = |V | sets, each having two vectors. All the vectors have p = |V | bits. For each vertex i of V , we create the set

V i = (v i 1 , v i 2 ). For any i, we define v i 1 = (v i 1 (1), v i 1 (2), . . . , v i 1 (p)), where v i 1 (k) = 1 iff {i, k} ∈ E or i = k, and v i 2 = (v i 2 (1), v i 2 (2), . . . , v i 2 (p)), where v i 2 (k) = 1 iff i = k.
In other words, v i 1 corresponds to the i th row of the adjacency matrix of G, with a self loop.

The idea is that selecting v i 1 corresponds to selecting vertex i in graph, and selecting v i 2 will turn the i th component to 0, which corresponds to a penalty for not choosing vertex i.

We first need to state an intermediate lemma. For any stack s = {v s 1 , . . . , v s m },

let Xs = {i|v s i = v i
1 } be the associated set of vertices in G. Recall that vs is the p dimensional vector representing s.

Lemma 1. ∀i ∈ [p]1, vs(i) = 1 ⇔ ((i ∈ Xs) and (∀x ∈ Xs \ i, {x, i} ∈ E)).
Let us first prove Lemma 1. Suppose i th component of vs is 1. This implies that v i 1 ∈ s, and thus i ∈ Xs. Now, suppose by contradiction that ∃x ∈ Xs \ i such that {x, i} / ∈ E. x ∈ Xs implies that v x 1 ∈ s. Moreover, vs(i) = 1 implies that v x 1 (i) = 1, and thus {x, i} ∈ E, which leads to a contradiction. Suppose now that i ∈ Xs, and ∀x ∈ Xs \ i, {x, i} ∈ E. Let us prove that ∀i , v s i (i) = 1. Notice first that for i = i we have

v s i (i) = v i 1 (i) = 1. Moreover, ∀i = i such that i / ∈ Xs we have v s i (i) = v i 2 (i) = 1. Finally, ∀i = i such that i ∈ Xs, we have v s i (i) = v i 1 (i) = 1 as {i , i} ∈ E.
It is now straightforward to prove that ∀x, "∃ solution S for max max 1 of value fmax 1 (S) = x ⇔ ∃ a clique X in G of size x." Indeed, suppose first that we have a solution S such that fmax 1 (S) = x. Let s = (v s 1 , . . . , v s m ) be the stack in S of value x, and let Gs = {k|vs(k) = 1} be the set of good bits of s. We immediately get that the vertices corresponding to Gs form a clique in G, as ∀i and j ∈ Gs the previous property implies that i ∈ Xs, j ∈ Xs, and thus {i, j} ∈ E. Suppose now that there is a clique X * in G, and let s be a stack such that Xs = X * . The previous property implies that ∀i ∈ Xs, vs(i) = 1.

Thus, Optmax max 1(I ) is equal to the size of the maximum clique in G. As the previous reduction is polynomial, and as a solution of S of I can be translated back in polynomial time into the corresponding clique in G (of same size), we get the desired result.

As for any there is no O(|V | 1-)-approximation for Maximum Clique Problem (with set of vertices V ) unless P=NP [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF], we get the following corollary: Corollary 2. Even for n = 2, for any , there is no ρ(m, p)-approximation such that ρ(x, x) = O(x 1-) for max max 1 and thus for max 1. Notice that in particular, O(p 1-) and O(m 1-) are not possible, but for example (pm) 1 2 is not excluded.

To summarize, the main negative results for max 1 are no O(p 1-)-approximation and no O(m 1-) approximation for n = 2, and no O( m ln m )-approximation for arbitrary n (using the reduction from k-Dimensional Matching of [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF]). Notice that it does not seem obvious to adapt the previous reductions to provide the same non-approximability results for min 0. Thus, the question of improving the f (m) ratios provided in [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF] is still open.

Positive Results

In this Section, we develop some polynomial-time approximation algorithm for max 1. Then, we show that max 1 and min 0 are FPT parameterized by p.

p

r -approximation Given the previous negative results, it seems natural to look for ratio p r , where r is a constant. Let us first see how to achieve a ratio p with Algorithm 1.

Property 1. Algorithm 1 is a p-approximation algorithm for max 1.

Algorithm 1: p-approximation for max 1 x = 0; while ∃k such that it is possible to create a stack s such that v s (k) = 1 do Add s to the solution;

x = x + 1; if x < n then
Add n -x arbitrary (null) stacks to the solution;

Proof. Let S = S =0 S0 be the solution computed by the algorithm, where S =0 is the set of non zero stacks, and S0 is the set of the remaining null stacks. Since S =0 and S0 are disjoint, we have S0 = S \ S =0. Let n1 = |S =0|, and ∀i, let

V i = V i S0. Let n2 = |S0| = |V i | (all the V i have the same size). Notice that n = n1 + n2.
As the algorithm cannot create any non null stack at the end of the loop, we know that for any position k ∈ [p]1, there is a set i(k) such for any vector w ∈ V i(k) , w(k) = 0. In other words, we can say that there is a column of n2 zeros in set V i(k) . Notice there may be several columns of zeros in a given set. Thus, we deduce that there are at least p columns (of n2 zeros) in the vectors of V i(k) . Moreover, as none of these zeros can be matched in a solution, we know that these n2p zeros will appear in any solution.

Thus, given S * an optimal solution, we have f (S * ) ≤ np -n2p = n1p. As f (S) ≥ n1, we get the desired result.

Given a fixed integer r (and targeting a ratio p r ), a natural way to extend Algorithm 1 is to first look for r t-tuples (i.e. find (k1, . . . , kr) such that it is possible to create s such that vs(k1) = • • • = vs(kr) = 1)), then (r -1) t-tuple, etc. However, even for r = 2 this algorithm is not sufficient to get a ratio p 2 , as shown by the example depicted in Figure2. Fig. 2. Counter-example showing that Algorithm 1 for r = 2 remains a papproximation. The depicted stacks correspond to an optimal solution of profit 3 whereas the algorithm outputs a solution of profit 1.

V 1 V 2 V 3 V 4 V 5 V 6 S
In this example it is not possible to create any stack of value strictly greater than 1 since set V 1 kills positions {1, 2} (we say that a set kills positions {k1, k2} iff there is no vector in the set such that w(k1) = w(k2) = 1), set V 2 kills positions {1, 3}, and set V 3 kills positions {2, 3}.

Thus, in this case (and more generally when no stack of value greater than 1 can be created), the solution computed by the algorithm for r = 2 is the same as one computed by Algorithm 1. In the worst case, the algorithm creates only one stack of value 1 (by choosing the first vector of each set). However, as depicted in Figure 2, the optimal value is 3, and thus the ratio p 2 is not verified.

In other words, knowing that no stack of profit 2 can be created does not provide better results for Algorithm 1. This motivates the different approach we follow hereafter.

Property 2. Suppose that there exists an exact algorithm for max 1 running in f (n, m, p). Then, for any r ∈ [p]1 we have a p r -approximation running in O(p × f (n, m, r)).

Proof. The idea is to use a classical "shifting technique" by guessing the subset of the r most valuable consecutive positions in the optimal solution, and run the exact algorithm on these r positions. Let S * be an optimal solution for max 1. For any k, let Ik be the restricted instance where all the vectors are truncated to only keep positions in Xk (there are still nm vectors in Ik, but each vector is now a r dimensional vector). By running the exact algorithm on all the Ik and keeping the best solution, we get a p r -approximation running in O(pf (n, m, r)).

The previous lemma motivates the exact resolution of max 1 in polynomialtime for fixed p. It is already proved in [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF] that min 0 can be solved in O(m(n 2 p )). As this result also apply to max 1, we get a p r -approximation running in O(pm(n 2 r )), for any r ∈ [p]1. Our objective is now to improve this running time by showing that max 1 (and min 0) are even FPT parameterized by p (and not only polynomial for fixed p).

Faster algorithm for fixed p for max 1

Definition 1. For any t ∈ [2 p -1]0, we define configuration t as Bt: the pdimensional binary vector that represents t in binary. We say that a p-dimensional vector v is in configuration t iff v = Bt.

First ideas to get an FPT algorithm

Let us first recall our previous algorithm in [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF] for fixed p. This result is obtained using an integer linear programming formulation of the following form. The objective function is min 2 p -1 t=0 xtct (recall that in [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF] the considered objective function is min 0), where xt ∈ [n]0 is an integer variable representing the number of stacks in configuration t, and ct ∈ [p]0 is the number of 0 in configuration t.

This is a good starting point to get an FPT algorithm. Indeed, if we note nvar (resp. mctr) the number of variables (resp. number of constraints) of an ILP, for any A ∈ Q nvar ×m ctr , b ∈ Q m ctr , the famous algorithm of Lenstra [START_REF] Lenstra | Integer programming with a fixed number of variables[END_REF] allows us to decide the feasibility of an ILP, under the form ∃?x ∈ Z nvar |Ax ≤ b, in time

O(C n 3 var m O(1)
ctr ) (this running time is given in [START_REF] Kratsch | On polynomial kernels for integer linear programs: Covering, packing and feasibility[END_REF]), where C is a constant. Thus, to get an FPT algorithm parameterized by p, it is sufficient to write min 0 (and max 1) as an ILP using f (p) variables.

However, it remains now to add constraints that represent the min 0 problem. In [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF], these constraints are added using z i jt variables (for i ∈

[m]1, j ∈ [n]1, t ∈ [2 p -1]0))
, where z i jt = 1 iff v i j is assigned to a stack of type t. Nevertheless these new O(mn2 p ) variables prevent us to use [START_REF] Lenstra | Integer programming with a fixed number of variables[END_REF]. Thus, we now come back to the max 1 problem, and our objective is to express the constraints using only the {xt} variables.

Presentation of the new ILP for max 1

For any t ∈ [2 p -1]0, we define an integer variable xt ∈ [n]0 representing the number of stacks in configuration t. Let also ct ∈ [p]1 = c(Bt) be the number of 1 in configuration t. Definition 4. Given a profile P , an associated solution S is a solution such that P r(S) = P . We say that a profile P is feasible iff there exists an associated solution S that is feasible.

Notice that the definition of associated solutions also applies to a non feasible profile. In this case, any associated solution will also be non feasible.

Obviously, the max 1 problem can be formulated using the following ILP:

max 2 p -1 t=0 xtct subject to 2 p -1 t=0 xt = n ∀0 ≤ t < 2 p , xt ∈ N P = {xt}
is feasible Our objective is now to express the feasibility of a profile by using only these 2 p variables. Roughly speaking, the idea to ensure the feasibility is the following. Let us suppose (with p = 2 and n = 4 for example) that there exists a feasible solution of fixed profile x0 = 0, x1 = 1, x2 = 2, x3 = 1. Suppose also that the first set is as depicted in Figure 3. To create a feasible solution with this profile, we have to "satisfy" (for each set V i ) the demands xt for all configurations t. For example in set 1, the demand x2 can be satisfied by using one vector in configuration 2 and one vector of configuration 3, and the demand 3 can be satisfied using the remaining vector of 3 (the demand x0 is clearly satisfied). Notice that a demand of a given configuration (e.g. configuration 2 here) can be satisfied using a vector that "dominates" this configuration (e.g. configuration 3 here). The notion of domination will be introduced in Definition 5. Thus, a feasible profile implies that for any set i there exists a perfect matching between the vectors of V i and the profile {xt}.

Let us now define more formally the previous ideas.

Definition 5 (Domination).

A p-dimensional vector v1 dominates a p-dimensional vector v2 (denoted by

v1 v2) iff ∀k ∈ [p]1, v2(k) = 1 ⇒ v1(k) = 1. 10 • 01 • 11 • 11 • V 1 P 01 • 10 • 10 • 11 • Fig. 3.
Example showing that satisfying demands of profile P with set 1 requires to find a perfect matching. Edges represent domination between configuration.

A configuration

t1 ∈ [2 p -1]0 dominates a configuration t2 ∈ [2 p -1]0 (denoted by t1 t2) iff Bt 1
Bt 2 (recall that Bt is the p-dimensional binary representation of t).

A solution S dominates a solution S (denoted by S S) iff ∃ a bijection φ :

[n]1 → [n]1 such that for any i ∈ [n]1, v s i
vs φ(i) (in other word, there is a one to one domination between stacks of S and stacks of S).

A profile P dominates a P (denoted by P P ) iff there exists solutions S and S such that P r(S ) = P , P r(S) = P and S S. Definition 6. For any i ∈ [m]1 and any t ∈ [2 p -1]0, let b i t be the number of vectors of set V i in configuration t. Definition 7 (Graph G i P ). Let P be a profile not necessarily feasible. Let G i P = ((∆P , Λ i ), E ), where

Λ i = {λ i,l t , 0 ≤ t ≤ 2 p -1, 1 ≤ l ≤ b i t }, and ∆P = {δ l t , 0 ≤ t ≤ 2 p -1, 1 ≤ l ≤ xt}.
Let us fix a bijection f : ∆P ∪ Λ i → [2 p -1]0, that associates to each vertex λ i,l t and to each vertex δ l t the vector in configuration t. Λ i (resp. ∆P ) represents the set of vectors of V i (resp. the demands of profile P ) grouped according to their configurations. Notice that

|Λ i | = |∆P | = n. Finally, we set E = {{a, b}|a ∈ ∆P , b ∈ Λ i , f (a) f (b)}.
We are now ready to show the following proposition.

Proposition 1. For any profile P = {x0, . . . , x2p-1}, (∃P feasible, with P P ) ⇔ ∀i ∈ [m]1, ∃a matching of size n in G i P Before starting the proof, notice that the simpler proposition "for any P , P feasible ⇔ ∀i ∈ [m]1, there is a matching of size n in G i P " does not hold. Indeed, ⇒ is correct, but ⇐ is not: consider P with x0 = n (recall that configuration 0 is the null vector), and an instance with nm "1 vectors" (containing only 1). In this case, there is a matching of size n in all the G i P , but P is not feasible. This explains the formulation of Proposition 1. An example of the correction formulation is depicted Figure 4.

Proof. Let P be a profile.

(⇒) Let P be a feasible profile that dominates P . Let S = {s1, . . . , sn} and S = {s 1 , . . . , s n } two solutions such that S is feasible, P r(S) = P , P r(S ) = P (notice that S and P are not necessarily feasible), and S S. Without loss of generality, let us assume that ∀j, s j sj (i.e. the bijection φ of Definition 5 is the identity), and let us assume that for any j, s j = (v 1 j , . . . , v m j ). Since v i j ∈ s j , then for any f (δj) creates another vector that dominates f (δj). Thus, S is feasible, and P r(S) P , and we set

1101 • λ 1,1 13 0110 • λ 1,1 6 1110 • λ 1,1 14 V 1 Λ 1 0101 • λ 3,1 5 1110 • λ 3,1 13 0110 • λ 3,1 6 V 3 Λ 3 0111 • λ 2,1 7 1111 • λ 2,1 15 1110 • λ 2,1 14 V 2
P = P r(S).
Now, we can use the famous Hall's Theorem to express the existence of a matching in every set.

Theorem 3 (Hall's Theorem

). Let G = ((V 1 , V 2 ), E) a bipartite graph with |V 1 | = |V 2 | = n. There is a matching of size n in G iff ∀σ ⊆ V 1 , |σ| ≤ |Γ (σ)|, where Γ (σ) = {v2 ∈ V 2 |∃v1 ∈ σ such that {v1, v2} ∈ E}.
Remark 1. Notice that we cannot use Hall's Theorem directly on graphs G i P , as we would have to add the 2 n constraints of the form ∀S ⊆ V i . However, we will reduce the number of constraints to a function f (p) by exploiting the particular structure of G i P . Proposition 2 (Matching in G i P ).

∀i ∈ [m]1, ∀P = {x0, . . . , x2p-1}:

(∀σ ⊆ ∆P , |σ| ≤ |Γ (σ)|) ⇔ (∀σcfg ⊆ [2 p -1]0, t∈σ cf g xt ≤ t∈dom(σ cf g ) b i t )
where dom(σcfg) = {t |∃t ∈ σcfg such that t t} is the set of configurations that dominate σcfg.

Proof. (⇒) Let

σcfg = {t1, . . . , tα}. Let σ = {δ l t i , 1 ≤ i ≤ α, 1 ≤ l ≤ xt i } be the vertices of ∆P corresponding to the demands in σcfg. Observe that t∈σ cf g xt = |σ|. Notice also that Γ (σ) = {λ i,l t , t ∈ dom(σ), 1 ≤ l ≤ b i t } by construction. Thus, |σ| ≤ |Γ (σ)| implies t∈σ cf g xt ≤ t∈dom(σ cf g ) b i t . (⇐) Let σ ⊆ ∆P . ∀t ∈ [2 p -1]0, let Xt = {δ l t , 1 ≤ l ≤ xt}, let σt = σ Xt. Let σcfg = {t1, . . . , tα} = {t|σt = ∅}. Let X = t∈σ cf g {Xt}. Notice that |σ| ≤ |X| = t∈σ cf g xt.
Let us first prove that Γ (σ) = Γ (X). Γ (σ) ⊆ Γ (X) is obvious. Now, if there is a λ i,l t ∈ Γ (X), it means that there is a t ∈ σcfg such that λ i,l t ∈ Γ (Xt), and thus there exists l such that {δ l t , λ i,l t } ∈ E (which implies that t t). As σt = ∅, there exists l such that δ l t ∈ σt, and {δ l t , λ i,l t } ∈ E as t t.

Finally, the hypothesis with our set σcfg leads to

|σ| ≤ |X| = t∈σ cf g xt ≤ t∈dom(σ cf g ) b i t = |Γ (X)| = |Γ (σ)|
Using Propositions 1 and 2, we can now write that for any profile P = {x0, . . . , x2p-1}:

∃P feasible, with

P P ⇔ ∀i, ∀σcfg ⊆ [2 p -1]0, t∈σ cf g xt ≤ t∈dom(σ cf g ) b i t .
Thus, we use now the following ILP to describe the max 1 problem:

max 2 p -1 t=0 xtct subject to ∀i ∈ [m]1 : ∀σcfg ⊆ [2 p -1]0, t∈σ cf g xt ≤ t∈dom(σ cf g ) b i t ∀t ∈ [2 p -1]0, xt ∈ N
This linear program has 2 p variables and (m2 2 p + 2 p ) constraints. Thus, we can solve it using [START_REF] Lenstra | Integer programming with a fixed number of variables[END_REF] in time f (p)poly(n+m), we get that max 1 and min 0 are FPT parameterized by p. Using Property 2 this ILP leads to a p r -approximation algorithm for max 1 running in time f (r)poly(n + m).

Conclusion

In this article, we established that max 1 is O(m 1-ε ) and O(p 1-ε ) non-approximable for n = 2. On the positive side, we provided a FPT algorithm for max 1 leading to a p r -approximation algorithm running in O(f (r)poly(m + n)), which is the best we can hope for. The existence of a ρ(m)-approximation (typically m) algorithm remains open. arbitrary stacks (as these stacks use in each of the first m -1 set the set X of null vectors, the value of these stacks is zero). Thus, we get f 1 (S) = x.

Let us new check that "∀ solution S of max 1, ∃ solution S of max =0 of value fmax 1 (S ) ≥ f =0(S ). As any vector of set m has only one good bit (i.e.equal to 1), the profit of any stack of S is at most 1, and thus there is exactly x non null stacks {s1, . . . , sx} in S. By removing the vector in set m in each of these x stacks, we get x non null stacks of I . Finally, we complete the construction of S by creating arbitrarily the n -x remaining stacks, and we get f =0(S ) ≥ x (notice that the value of S can be greater than x, as we could have a null stack si ∈ S whose restriction to the first (m -1) set is a non null stack of I ).

Thus, we get Optmax =0 (I ) = Optmax 1(I ). As the previous reduction is polynomial, and as a solution of S of I can be translated back in polynomial time into a solution S of I with f =0(S ) ≥ f 1 (S ), we get the desired result.

We now prove that max =0 is harder than kDM. But first of all, let us recall the k Dimensional Matching problem. Theorem 2 (implicit in [START_REF] Dokka | Approximation algorithms for the wafer to wafer integration problem[END_REF]). For any ρ(m), any polynomial ρ(m)-approximation algorithm for max =0 can be converted into a polynomial ρ(k)-approximation algorithm for the kDM problem.

Proof. Let us consider an instance of kDM described by k sets Xi, 1 ≤ i ≤ k (where Xi are pairwise disjoint) such that |Xi| = n, and x k-tuple tl ∈ X1 × • • • × Xk, 1 ≤ l ≤ x. We denote by a j i , 1 ≤ j ≤ n the elements of set Xi. From this instance, we construct an instance of max =0 composed of k sets, each containing n vectors. The number of bits per vector is equal to x. Vector j of set i represents the set of k-tuple that use element a j i . Thus, we define v i j as a string of size x, where the k th bit is set to 1 iff a j i is used in tk. Thus, the k th bit of a stack is 1 iff each element of tuple k is selected (by selecting corresponding vector), and then iff tuple t belongs to solution of kDM instance. Notice that the value of any stack is at most 1, since a stack represents a tuple.

Fig. 1 .

 1 Fig. 1. Example of max 1 instance with m = 3, n = 4, p = 6 and of a feasible solution S of profit fΣ1(S) = 7.

  ln m ) inapproximability for any ε, O(p 1-ε ) and O(m 1-ε ) inapproximability (even for n = 2) polynomial for fixed p p r -approximation in O(f (r)poly(n)) FPT/p min 0 for m = 3 : 4 3 -approximation, APX-hard FPT/p f (m)-approximation for general m polynomial for fixed p

k+1+ 3 in [ 2 Theorem 2 .

 322 ].Let us now consider a new reduction which provides results for n = 2 and according to parameter p. There is a strict reduction from Maximum Clique Problem to max max 1 for n = 2.

  Let us write f (S * ) = p k=1 ak, where ak = |{s ∈ S * |vs(k) = 1}| is the number of stacks in S * that save position k. ∀k ∈ [p -1]0, let Xk = {k, . . . , (k + r -1) mod p}, and σk = t∈X k at. Notice that we have p k=1 σk = r p k=1 ak = rf (S * ), as each value ak appears exactly r times in p k=1 σk. This implies maxk σk ≥ r p f (S * ).

Definition 2 .

 2 A profile is a tuple P = {x0, . . . , x2p-1} such that 2 p -1 t=0 xt = n. Definition 3. The profile P r(S) = {x0, . . . , x2p-1} of a solution S = {s1, . . . , sn} is defined by xt = |{i|vs i is in configuration t}|, for t ∈ [2 p -1]0.

Fig. 4 .

 4 Fig. 4. Illustration of Proposition 1 with m = n = 3 and p = 4. Left: The three G i P graphs (edges are depicted by solid and dotted lines), and three matchings (in solid lines) corresponding to S . Right: Solution S s.t. P r(S ) P .

  Inputk pairwise disjoint sets of n elements andx k-tuple tl ∈ X1 × • • • × Xk, 1 ≤ l ≤ x Output a set of disjoint k-tuplesObjective functionsmaximize the number of tuples in solution

  of Problems 2.

	Set of problems 2 max max 1 and max =0
	Input	m sets of n binary p-dimensional vectors
	Output	a set S of n disjoint stacks
	Objective functions	max max 1: maximize fmax 1(S) = max j∈[n] 1 c(vs j ), the profit of the best stack max =0 : maximize f =0 (S) = |{j|c(vs j ) ≥ 1}|, the number of non null stacks

  i, we know that v i Let us suppose that ∀i ∈ [m]1, there is a matching M i of size n in G i P . W.l.o.g.let us rename {δ1, . . . , δn} the vertices of ∆P , and {λ i 1 , . . . , λ i n } the vertices of Λ i such that for any i, M i = {{λ i Let us define S = {s1, . . . , sn}, where ∀j ∈ [n]1,

	j	s j	sj, ∀j ∈ [n]1. This implies a matching of
	size n in all the graphs G i P .
	(⇐) 1 , δ1}, . . . , {λ i n , δn}}. This implies
	f (λ i 1 ) f (δn). sj = (f (λ 1 f (δ1), . . . , f (λ i n ) j ), . . . , f (λ m j )). Notice that for any j, sj	f (δj), as all the f (λ i j )	f (δj),
	and combining two vectors f (λ i 1 j )		f (δj) and f (λ i 2 j )

The notation [n]j stands for {j, . . . , n}.

A Reduction from kDM

In this section, we provide the reductions proving that max 1 is harder than max =0 and that max =0 is even harder than kDM. Observation 2 There exists a strict reduction from max =0 to max 1.

Proof. Consider an instance I [m , n , p ] of max =0. We construct an instance I[m, n, p] of max 1 as follows. The number of components of each vector is left unchanged (p = p ), the number of vectors per set is multiplied by p (n = n p ) and the number of sets is increased by one (m = m + 1). ∀j = 1, . . . , m , the sets V j are constructed as follows: V i = V i X, where X contains n -n null vectors, and V m +1 contains n times the following sets of vectors (this is the reason why n = n p ): {1000 . . . 000 p=p , 0100 . . . 000, 0010 . . . 000, . . . , 0000 . . . 010, 0000 . . . 001}

As an example, the following instance

is turned into the following one I [START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF][START_REF] Niedermeier | Invitation to fixed-parameter algorithms[END_REF][START_REF] Dokka | Multi-dimensional vector assignment problems[END_REF] of max 1:

Informally, as the set V m of I turns any non zero stack of I into a stack of value 1 (by choosing an appropriate vector), maximizing the total number of 1 in I requires to maximize the number of non null stacks in I . Let us check first that "∀ solution S of max =0, ∃ solution S of max 1 of value f 1 (S) = f =0(S )". Let {s 1 , . . . , s x } be the x non null stacks of S , and {s x+1 , . . . , s n } be the null stacks of S . Let us now construct S. For any i, 1 ≤ i ≤ x, let ki be a non null bit in s i . We extend s i to a stack si by adding a vector v m j of set m such that v m j (ki) = 1. Notice that such a vector always exists as for any position k, 1 ≤ k ≤ p there are n wafers in set m whose bit in position k is equal to 1. Thus, even if the x stacks of S have the same non null position k, the previous construction is possible. Finally, the n -x remaining null stacks of S are extended arbitrarily, and we complete the construction of S by adding n -n


Jocelyne Streiff-Fénart

Biography Jocelyne Streiff-Fénart

Border control, urban trends and migrant trajectories in Nouadhibou (Mauritania

This chapter examines different forms of migrant integration in Nouadhibou, Mauritania. In this town, the activities developed by transit migrants have been integrated in the local economic network, which is largely articulated around the activities of waves of earlier migrants that have been instilled with a renewed dynamism by newcomers. Since the implementation of border surveillance measures in 2006, transit migration has been identified as the target of specific (police and humanitarian) practices assigned to specific actors. Within a matter of years, these mechanisms have produced an entirely new universe of people, practices, places, and technologies gravitating around "illegal" migration, and have also highlighted the situation of presumed "illegals" (either by stigmatizing them or by defending them). As a category of migration management developed in expert discourses, "transit migration" has produced the category of "transit" migrants, thus spelling the end of a conception of migration in which transitory residence was just one feature among others of migrant presence within the town.

This chapter examines different forms of migrant integration in Nouadhibou, Mauritania. Nouadhibou owes its distinctiveness to the history of its urban development and its position on "migration routes" 1 . Unlike other countries affected by the externalisation of migration management, Mauritania is only viewed as a transit country 2 . The main purpose of the measures taken by the EU (and the required cooperation of its partners in accordance with the policy of cooperation defined in the Rabat declaration) is to impede the passage of migrants of all origins transiting via the country by controlling the country's land borders and maritime borders towards Europe. Since the massive wave of migrations on pirogues in late 2005, Nouadhibou has been earmarked as a strategic location for testing the implementation of new border control measures [START_REF] Carrera | The EU border management strategy, Frontex and the challenges of irregular immigration in the Canary Islands[END_REF] and inter-state cooperation policies. The new measures include police cooperation using mixed patrol units as part of the Seahorse and Atlantis programmes, the Frontex programme (Hera II, starting in the summer of 2006), a new detention centre in Nouadhibou, and legal cooperation aimed at reinforcing migration legislation to regulate entries and exits3 (Streiff-Fénart & Poutignat 2009).

In the last decade, the reputation of Nouadhibou as a transit town coupled with the enforcement of border control measures assigned to specific towns have considerably increased the visibility of the populations targeted by the new measures -i.e. "transit migrants". This is not merely a reference to the effects of the new surveillance and refoulement measures automatically generating increasing numbers of migrants by retaining candidates for migration in a "net" (Migreurop) or holding them in a "cul-de-sac" [START_REF] Bâ | Tenter l'aventure par la Mauritanie: migrations transsahariennes et recompositions urbaines[END_REF]. Though useful for underlining the constraints exerted by migration policies on "thwarted mobilities" (Le Herou 2007), such views are misleading if they are taken literally. The majority of migrants using Nouadhibou as a point of departure usually remain in the town only for very limited periods. Candidates for migration tend to transit via Nouadhibou before heading for Europe on pirogues. If they fail to reach Europe, migrants head for other destinations (Nouakchott, Dakar, Morocco) or travel back and forth between these destinations. Those who stay in Nouadhibou for longer periods (in some cases several years) do so not because they are "blocked" (in the literal sense of the term4 ) but because they have found a niche -i.e. a job opportunity that has caused them to delay their plans, and in some cases to abandon them altogether.

The focus of this chapter is not the quantitative growth of migrant populations so much as their emergence as a new urban category. This chapter will examine more specifically how an abstract classificatory category (i.e. the notion of transit defined a decade ago by international agencies) has been "realized"5 in practice in a particular context: through funding networks (e.g. European invitations to tender, funding from foundations or international agencies) resulting in action programmes (dissuasion campaigns, training and assistance measures); by the creation of networks of actors (state agents, international experts, NGOs, local associations) connected via these programmes by cooperation, competition or customer relations; or through landmarks of migration located in the urban landscape (for example a detention centre known as 'Guantanamito' -a term coined by the immigrants themselves -is slowly emerging as an urban toponym).

To fully measure its scope and significance, the situation borne of the measures aimed at monitoring populations and controlling migrant movements needs to be viewed in its proper urban context -i.e. in the context of a town that has built its power as an economic capital on population movements related to labor. Since its creation by the administrators of French West Africa in 1906 under the name Port-Etienne, the urbanization of Nouadhibou has been founded on diverse populations involved in industrial, craft and service activities not provided by local populations, of nomadic and trading traditions. French administrators, Senegalese skirmishers, and fishermen and traders from the Canary Islands during the first period of urbanization were succeeded by labor migrations after the creation of Miferma in 1952 and the mineral port exporting iron extracted from the mines of Zouerate, by Russian, Korean and Chinese companies in industrial fishing, and by West African migrants involved in urban trades (construction, transport, catering, mechanics, cleaning, domestic services) [START_REF] Acloque Benjamin | Nouadhibou c'est déjà ailleurs ! Sur l'élaboration et la représentation sociale de l'espace urbain en milieu nomade[END_REF][START_REF] Bonte Pierre | La montagne de fer[END_REF].

As a result of constantly renewed migration flows in Mauritania, Nouadhibou has developed an image of a town particularly well-suited to lucrative business activities. Today its reputation has spread beyond the country's borders. Migrant movements have tended to involve both foreigners, particularly those involved in fishing (Senegalese, Malians, Ghanaians, Bissau Guineans...) and nationals, including Wolof fishermen from N'diago [START_REF] Abdou | Réseaux et groupes d'appartenance chez les pêcheurs migrants: le cas des Wolofs de N'Diago (Mauritanie)[END_REF], workers in the mining industry from the river region recruited during the colonial period (known during the Miferma era as the "displaced"), and state employees, who have tended to define themselves as "deported" pending their reassignment in the capital. The multiple forms of migrant circulation are reflected by equally multiple ways of "being foreign". One of the most distinctive characteristics of Nouadhibou is that it has been a migrant town since its inception, i.e. an intermediate place operating as a crossroads for a wide variety of migrant trajectories, though rarely an ending point (Poutignat & Streiff-Fénart 2001). Migrant trajectories include migrants transiting towards Europe, who began to view Nouadhibou as a potential place of transit in the 1980s, though not as commonly used as others (Barden 1993).

Migrants staying for longer periods in Nouadhibou pending an opportunity to travel on a fishing boat, to journey across the Sahara towards Morocco or (more recently) to leave on a pirogue have become a familiar urban figure in the last twenty years. The aim of many young men from Sub-Saharan Africa transiting via Nouadhibou is to "find the way". The term "adventurer" has been used to describe these migrants since the early 1990s, a label clearly in evidence on a "letter-box for adventurers" on the door of the Catholic mission (Poutignat & Streiff-Fénart 2001).

The activities developed by transit migrants have been integrated in the local economic network, which is largely articulated around the activities of waves of earlier migrants that have been instilled with a renewed dynamism by newcomers. This is particularly the case of traditional fishing and related activities. Since the 1990s, the presence of migrants has proved decisive for the development of informal economic activities based around fish processing (particularly the production of dried salted fish or fermented fish).

A historically minor activity sometimes left to fishermen's wives, fish processing was recently given a new lease of life by pioneers (Nigerians and Ghanaians) intent on promoting species not exploited by local factories exporting towards the foreign European market and destined for the domestic African market. In Nouadhibou, the fish processing centre is located in an area called Bûntiyya, situated near the traditional port and fishermen's quarter of La Charca (see photo 1). Both the urban space and the activities carried out in the area have to some extent been appropriated by "foreigners". The term refers (and this is precisely what makes the area so unique and distinctive) to a wide range of foreigners, from large-scale merchants who are long-term residents and have sometimes become national citizens to contract-men offering their labor on a daily basis pending their passage to Europe. The only reason why Bûntiyya has been appropriated by foreigners is that the activities carried out in the area have been left to migrants. A dirty, foul-smelling activity, fish processing has been largely abandoned by the native population, who may nevertheless derive a range of benefits from tolerating fish exploitation by foreigners -from various levies (soldiers regularly transit via the area to claim baksheesh) to the compulsory joint venture for business activities of any size, an obligation that must be complied with to avoid immediate sanction (which generally involves the offender having to leave the town).

Though it is a fragile operation subject at any point to potential evictions, Bûntiyya has become a centre of intense immigrant circulation in the last twenty years. Migrant movements in this area are based on overlapping migrant trajectories at different levels of the production process. Beyond the traditional cross-border production of guedj and wellestablished markets (such as shark fins exported to Asia controlled by Malian-Mauritanian joint ventures), the initiatives of adventurers have proved decisive in the development of the production and exportation of selachians (skates and sharks), which had previously remained confined to Nouakchott. In some cases, the commercial initiatives developed by migrants have even generated new markets (developed for instance by Nigerians) by bringing together potential buyers, spaces and resources in new and unexpected ways. For example, having noted how closely related a species of small sharks (called tollo) exploited in the Canary Islands appeared to be to a luxury product consumed in Nigeria by the higher classes, a handful of Nigerian adventurers set out to process and market the product as a cheap substitute on the Nigerian market (see photo 2).

Within a matter of years, Bûntiyya has become a transnational market place in the informal economy, largely as a result of the availability of cheap labor (precisely because migrants are merely transiting through the area), but also because the "adventurers" providing such labor have been able to alter their projects and to reinvest their earnings by becoming involved in the "fish business" (see the contribution of Poutignat in this volume). The values of the "adventurer" (a taste for risk, the determination to pursue an objective, a spirit of initiative, the courage to face danger, the ability to make sacrifices in order to accumulate capital and resources) are easily converted into the typically aggressive and innovative characteristics of the Schumpeterian entrepreneur. Bûntiyya has precisely been the site of such conversion for certain adventurers.

While very few migrants are successful and remain in business on a permanent basis, risktaking strategies can be beneficial for those able to call on relations and funds in their country of origin. The success of these migrants gives substance to the imaginary figure of the transnational entrepreneur (Peraldi 2002) who, alongside other figures (such as the figure of the footballer), symbolizes the hope of attaining a new status and reinforces the idea that Nouadhibou is the right place to achieve this goal.

The specific interest of Bûntiyya is that it highlights the particular type of urban cosmopolitanism that is characteristic of Nouadhibou within the confines of a small and clearly delimited space -i.e. the cosmopolitanism of a crossroads town of great mobility where dynamic business activities and work relations are built on embedded and overlapping migration trajectories. Because migrant projects may shift and change at any time, it may be difficult to draw a distinction between migrant workers, migrant traders and transit migrants.

As a result of the EU measures implemented in 2006 to reinforce "management capabilities" as part of the control of illegal migration in Mauritania, transit migration has been identified as the target of specific (police and humanitarian) practices assigned to specific actors. Following the introduction of new border surveillance measures, highly visible actors have begun to appear in town: coastguards and policemen from the Guardia Civil patrolling on speedboats and helicopters. The deployment of repressive measures has also been accompanied by the arrival of an entire fleet of international NGOs (Red Cross, Croissant Rouge, and Médecins du Monde) that have taken over the issue of humanitarian aid.

More recently, members of Mauritania's civil society have also become involved in defending so-called "illegal" migrants6 . Since the creation of a detention centre in Nouadhibou, the Mauritanian Association of Human Rights (AMDH), which had never previously worked in the town, and the Association for the Protection of the Environment and Humanitarian Action (APEAH), which had previously been specialized in environmental issues and the defence of refugees, have taken an active part in the defence or support of immigrants, alongside the Catholic Church and community associations. The latter had previously defended the interests of migrants indiscriminately, i.e. irrespective of their specific migrant status. Unlike what has tended to prevail in other contexts (for instance in Bamako), the individuals in charge of associations representing different communities (grouped under the leadership of Caritas within a federation) are often migrant adventurers who have abandoned their project more or less definitively, with a status halfway between association leader and president of a ghetto (Pian 2008, Laacher 2007) -hence the disappointment of the IOM, which, in an attempt to organize a meeting to encourage associations to join a programme of voluntary return, discovered that the associations themselves were "involved in illegal immigration" (interview with the senior representative of the IOM in Nouakchott, July 2007).

The Catholic Mission counts a very small number of labor migrants among its flock. It has been working for many years to provide help and assistance to migrant adventurers. The migrant statuses of their target audience are nevertheless uncertain. The Mission itself contributes to the reversibility of migrant trajectories, by offering jobs to the most highly qualified adventurers (trainers, cooks, secretarial work) and by providing migrants with a degree of stability for the duration of their stay in Nouadhibou. During celebrations, longterm immigrants, who represent its mainstay and are often settled "adventurers" (with wife and children), rub shoulders with transit migrants in town only for the duration of mass.

The practices and discourses of the new actors providing aid and assistance to immigrants (AMDH and APAH) are indicative of the rapid changes (since 2006) that have reconfigured the migration issue. Because of their connections with global networks defending undocumented and deported immigrants (Migreurop, Cimade) or the funding they receive from transnational agencies or NGOs (HCR, NGO OSIWA Soros Foundation), these associations tend to adopt the globalized management lexicon or militant vocabulary of organizations specializing in international migration. Locally, the meanings of migration are reinterpreted as the fight against illegal migration or the defence of Human Rights. In so doing, they contribute to a more general process of designation of transit migrants, identifying them (through terms such as "clandestines", "illegals", "transit migrants", "undocumented") as a specific problem or cause, and extracting their situation from the general condition of immigrants.

The denial of the rights of foreigners was common in Nouadhibou well before the town was identified as one of the main transit areas of illegal migrants heading for Europe. The local authorities had begun to enforce regular deportation procedures under pressure from the EU as early as the mid 1990s, though fairly leniently (as illustrated by the many jokes implying that the deported migrants returned to Nouadhibou before the policemen in charge of deporting them). The very same authorities occasionally resorted to particularly tough methods for expelling undesirable migrants, as illustrated in 2003 by the case of a Cameroonian national expelled for having levelled accusations at several businessmen and the Mauritanian government in a report broadcast on the French television channel FR3.

Though a less spectacular trend, immigrants have also been the target of all sorts of levies and "inconveniences" that have become so routine that the easiest and least damaging ways of complying have become part and parcel of the basic know-how of immigrants (i.e. shared knowledge of the basics that newcomers learn quickly on the advice of longer-established migrants) -for instance that it may sometimes be useful to remind the Moors of the presence in their own country of tradesmen who are just as likely to be the target of harassment; that it is unnecessary and dangerous to appeal to the justice system to obtain compensation for any harm suffered at the hands of an unfair employer or owner; or that migrants need to be able to recognize the point beyond which customs officers, the police or the military should not go (for example agreeing to give 500 oughia7 , but not 1000).

Following the measures implemented under EU pressure in 2006, the number of police controls has significantly increased, enhancing the precarity of the conditions of migrant residence and transit. 6000 people were thus held in a detention centre in 2006. The same year, Mauritania expelled 11,637 migrants. There is a widespread feeling among migrants that their relations with the local population have deteriorated significantly8 . There is also a sense of increasing hostility towards migrants (even among long-term settlers), while newcomers frequently complain of a lack of respect shown towards them by native Mauritanians. Though hardly meriting the top prize for hospitality (a distinction that goes unquestionably to Mali), Mauritania had previously been considered to be one of the more welcoming countries. The Catholic mission has even been forced to abandon its traditional trip to the beach because the procession of a group of Sub-Saharan walkers led by the local priest was recently mistaken for a meeting between illegal immigrants and smugglers. Locals can also be seen applauding cars returning expelled migrants to the border.

Beyond the matter of migrants' declining living conditions, the more general issue is the redefinition of the local representations (based on social tolerance and economic complementarity) that have been reconfigured politically as a "migration issue" determined by external European objectives.

Despite the suddenness of recent developments, there is no evidence of any direct connection with the influx of candidates for migration in the town since the end of 2005. The presence of young Sub-Saharan migrants, wandering in town or gathering in front of Western Union branches, has generated instead a mixture of curiosity and compassion rather than hostility. In March 2006, a migrant from the Ivory Coast even underlined the good relations between immigrants on the one hand and the authorities and the local population on the other:

When that thing happened in Nouadhibou (i.e. the increasing number of migrants leaving on pirogues), I have to say that the police and the gendarmes didn't really bother the foreigners at all [...] They tried to control the seashore, where young people got aboard, but they certainly didn't put any pressure on us or grab us in broad daylight [...] When all that fuss was going on, no one bothered us. Here the Mauritanian people I know, have actually been giving us advice, saying things like: "that's not good, you'll die, try to work here, it'll be ok, it'll work out", so you see they encouraged us, saying things like: "it'll be difficult, but try and work, there's oil coming, that'll bring in some money".

The changing representation of migrants was further driven by the introduction of new police methods. Despite the declining number of departures as a result of tougher controls 9 , the EU kept up its pressure on Mauritania, a country known for its leniency. In the absence of flagrante delicto, preventative arrests (i.e. raids in households, arrests on the street at night) became standard practice in order to maintain the high numbers of expulsions and deportations. According to unconfirmed rumours circulating among immigrants, raids tend to occur when the number of detainees at Guantanamito declines below a certain threshold, and there are even suggestions that money changes hands between the Spanish authorities and the Mauritanian police in an effort to reach official targets. The emergence of new police practices has had several significant consequences. It has generated new possibilities in a specific sector of the transit economy, the extortion market, and has increased the number of potential beneficiaries. According to several testimonies, the threats of denunciation have developed significantly and are no longer the sole prerogative of police employees.

Because of the close cohabitation of labor migrants and adventure migrants in Nouadhibou, the most significant impact of the new procedures is that preventative arrests are applied indiscriminately to all immigrants, to the point of threatening settled immigrants (including long-term settlers) with the possibility of police harassment, which was not intended in theory to be directed at them.

It's a real problem, because they can't see the difference. They just don't understand. That's what wears us down. They arrest people in their own homes because of illegal migrants. It's just not right.

(Account given by a Malian immigrant who has worked as a driver in Nouadhibou for ten years10 )

In addition to stigmatizing transit migrants or "clandestine" or "illegal" migrants (which they are often not), the recent measures have also undermined intra-community solidarity. While police officers are incapable of operating a selection using nothing more than the sole criterion of the intention to leave, the members of the community are by contrast "in the know".

The problem is that the workers and the people who leave live in the same place. In homes with 8 or 9 bedrooms, there'll be 2 or 3 bedrooms with people who want to leave. Instead of arresting the people in the two bedrooms, they'll arrest everyone. If you tell them who you are, they won't listen. We know, because they're our fellow countrymen, but the police don't bother to make the distinction.

The danger that the foreign population as a whole will become contaminated with the stigma of the targeted category has arisen in a political context marked by rising nationalist sentiments recommending (among others things) the "Mauritanization of jobs". The winner of the most recent general elections, General Azziz, is in the process of developing a new state discourse that has been described by his political opponents as "populist". The fishing sector provides an illustration of the new discourse, with certain species banned for export in order to preserve them for national consumption. A more recent consequence of the rise of nationalist tendencies is the priority given to national citizens in jobs, leading the government to reactivate the measures of the Code du Travail (labor law). These measures, which have yet to be enforced, require foreigners to hold a work permit.

The January 27 2009 issue of Le Calame published a report that claimed that an inspection carried out by the Ministry of Mining in the gold mines of Adjouj found that fifteen foreign workers (for the most part Ghanaians) were present on the site, "in violation of the measures relating to visas, work permits and staff qualification". The increasing number of inspections in the fishing sector (particularly in fish factories that employ large numbers of Senegalese workers) is designed to remind factory managers that a work permit is an absolute requirement for employing foreign workers.

The increasingly hard line taken by the state on labor legislation has been reflected in new institutional discourses and practices (training, positions adopted by unions) concerning the rights of migrant workers. However, the manner in which the new practices have been implemented is not altogether unambiguous. For instance, while awareness campaigns have been addressed exclusively to migrants (who are urged to register and to turn down any job without a contract, to file a complaint if they suffer a wrong at the hands of their employer), migrant workers are totally deprived of the power to enforce their rights. Attempts to promote the status and identity of migrant worker hardly resonate among migrants, who (despite being very hard workers) rarely seek to be identified as workers not least because many of them live in a state of indetermination -either because they view their situation as a form of temporary exile or because work is merely a transitional period before their passage to Europe or a conversion to a trading or entrepreneurial status.

Indetermination is precisely the issue that is challenged by the risk of contamination, as illustrated by the following extract taken from an interview with the President of the APEAH discussing the deteriorating conditions of immigrants in the town:

All immigrants are considered to be suspects, and what's even worse is that arrests tend to be made purely on the basis of physical appearance -so if you see someone who looks like they might be from Ghana or Sierra Leone, you arrest them, you grab them off the street, and you say they're an illegal migrant. In fact, the President of the Malians gave an example of this during training. He told us that he knew Malians who were serious and earnest and had come here to work and who were arrested on the street and expelled although they hadn't come here on their way to somewhere else.

The search for illegal migrants and the suspicion hanging over Sub-Saharan foreigners as a whole have increased the tendency to give greater substance to the transit migrant category and to demarcate transit migration from 'virtuous' labor migration in order to preserve the legitimacy of the latter. The division of the immigrant population into two distinct categories which had previously been closely intertwined, i.e. settled migrants and clandestines or illegals, between those migrating "to find work" and those migrating for other reasons, has become imbued with moral values: the values of labor migrant (earnest, honest) as opposed to the values of the migrant adventurer, viewed as idle, a potential delinquent, and even irreligious because, given the potentially lethal risks of their undertaking, adventurers challenge the condemnation of suicide by the revealed religions 11 .

The tendency to stigmatize illegal immigrants has not (so far?) resulted in xenophobic press campaigns such as those carried out in Morocco (Pian 2009). The migration issue in 11 A document on illegal migrations in Mauritania commissioned by the Soros Foundation recommended the enrolment of imams in dissuasion campaigns (Les tendances migratoires clandestines en Afrique de l'Ouest, Open Society Initiative for West Africa, 2008, p.69).

Mauritania has not fully entered the public sphere because it has never been instrumentalized in election campaigns (including the most recent campaign in 2009). Both the press in Nouakchott and the local press in Nouadhibou only devote a limited and relatively benevolent space to the issue of illegal immigration. More than migrants, independent newspapers denounce the violation of human rights, the complicity of state agents with smugglers, and the seizure of the possessions of "clandestines" for their own personal use (particularly mobile phones). One journalist observed recently: "why aren't possessions simply returned to the illegal migrants or to the leaders of their respective communities? After all, nobody has ever claimed that the pursuit of happiness in a foreign land was a crime".

The effects of the stigmatization of transit migrants have been felt more strongly in specific forms of organization developed among migrants than in the Mauritanian public sphere. One significant (and so far unique) example is the Malian community, the largest migrant community along with the Senegalese community (approximately 5000 to 6000 migrants in Nouadhibou). In a community in which adventure migrations have added to established labor migration trends, transiting immigrants tend to cohabit in large collective hostels (holding up to 500 people) with their fellow countrymen, whose familiar presence on the urban landscape is the product of traditional networks of local West-African migrations. The association representing their interests devotes its energies to reception and cultural and leisure activities, and is closely connected with the Ministry of Malian expatriates. It plays a quasi diplomatic role of representation and negotiation with the local authorities and provides protection to all Malian nationals.

The association has been rivalled since early 2009 by a new association claiming 700 members. The initiator of the new association, a well-educated and enterprising young businessman, presents himself as the defender of the interests of young people keen to take responsibility for their own lives and to claim their rights against older migrants deemed to be not sufficiently aggressive. The new association has sought to demarcate itself from the older association, described as "stodgy" and traditional. Its objective is to attract sponsors in order to fund concerts, gala dinners, and conferences aimed at promoting an image of foreigners as diligent, honest and well-integrated workers, far from the established stereotypes of illegal migration. The bylaws of the association include the obligation to ensure that official documents are in order and to register with the police, and not to defend fellow countrymen suspected of being illegal migrants or delinquents.

Now they don't draw any distinction between those who leave and those who come here to work. So our association wants to ensure that a clear distinction is made between illegal migrants and migrants [...] If somebody is caught red-handed, if you commit a crime, we won't defend you.

Under the air of a conflict of generations between ancients and moderns, old and young, another purpose of the attempt to "modernize" the association system is to introduce new arrangements in a system of transactions long-established in Mauritania and Africa more generally (Olivier de Sardan 1996). While the formalization of the immigrant worker status recommended by the association may serve to restrict the level of corruption in local authorities (racketeering, bribery, baksheesh), it can also be used for the purposes of paternalist practices of patronage that benefit the most affluent and longest-established migrants. It is no coincidence that the president is also the managing director of a brokerage company and that the honorary president of the association is the oldest Malian to have made his fortune in the fin trade. The president has made no attempt to conceal his objectives for regulating the recruitment and placing of workers by establishing himself as an intermediary in the main employment sectors for Malians -i.e. domestic services and traditional fishing. In traditional fishing, the issue in the long term is the constitution of permanent teams of workers organized in the same company, taking over from migrant adventurers, who represent at the moment the bulk of the contract men (the status of day laborer being, as noted above, well suited to their mobility, prepared as they are to move from one day to the next).

We have the labor, people who are willing to work and who are fit, serious and healthy. (President)

The company's aim to implement formal mechanisms for regulating the migrant labor market (an unprecedented measure in Nouadhibou) is congruent with the injunctions of the IOM and of the EU to modernize migration law and with the ambition of the State to restructure the labor market, particularly in the fishing sector. The company has also been given the approval of NGOs that recommend the legal formalization of work contracts to eradicate arbitrary treatment and exploitation, common issues in the informal sector.

There's already been some progress in the Malian community, since they have a representative which all employers have to deal with and who centralizes everything. Further evidence of the recent efforts to formalize regulation practices among immigrant groups is provided by the development of a new market, which, though smaller than in Nouakchott, is beginning to emerge in Nouadhibou: the market of "projects" aimed at the management of immigration. The issue of competition for access to resources is raised by the emergence of actors positioning themselves on the tender market for study programmes on the situation of "illegals" or information or "awareness" campaigns (on AIDS, the dangers of illegal emigration, the rights of immigrants). The new Malian association has again prefigured recent changes by forging links with the APEAH, which has placed it in pole position for the redistribution of this potential source of funding. But other associations who are now beginning to be in a position to be solicited as intermediaries are also starting to claim their share. In its July 2009 meeting (attended by the author), the federation of associations of foreigners included the definition of internal bylaws on its agenda designed to specify the form of cooperation with NGOS and sponsors "taking account of all the communities".

The new association of Malians and its president could be viewed as prefiguring recent developments that have combined to demarcate labor migrations from transit migrations: the implementation of strategies aimed at limiting the spread of the stigma of illegality; the initiatives aimed at regulating and formalizing labor immigration; the development of a market for the provision of surveys and migration awareness programs in which settled migrants are placed by NGOs and the international agencies serving as intermediaries for those among their fellow countrymen suspected of being illegal migrants.

Conclusion

The particular interest of the case of Nouadhibou is the sheer speed of the changes observed in the town following the introduction of European border control mechanisms implemented since 2006.

Within a matter of years, these mechanisms have produced an entirely new universe of people, practices, places, and technologies gravitating around "illegal" migration, and have also highlighted the situation of presumed "illegals" (either by stigmatizing them or by defending them). As a category of migration management developed in expert discourses, "transit migration" has produced the category of "transit" migrants, thus spelling the end of a conception of migration in which transitory residence was just one feature among others of migrant presence within the town.

In addition to other recent developments, this has resulted in changes which, beyond (or through) illegal immigration, have gradually affected all of the relations between immigrants and the local society. In keeping with its role as "economic capital", the urban model of Nouadhibou was characterized by a marked degree of ideological continuity between the spirit of entrepreneurship and migration (whether labor migration or adventure migration). The currently prevailing situation is underpinned by a systematic distinction between the local population and immigrants, but also between different types of immigrants (settled and transit migrants) insofar as even the settled migrants (or at least some of them) have contributed significantly to the selection process.

It remains to ask what generalizable conclusions might be drawn from this distinctly monographic study. It is important to note first of all that the monographic aspect of this study is an inherent feature of the phenomenon under study. The externalisation policy is implemented differently according to the position of southern countries on migration routes and the objectives assigned to them within the partnership (i.e. "keeping people at home or immobilizing them en route", Morice 2008). The opening of the legal labor market to contingents of nationals in Mali and Senegal (viewed as sending countries) is at the heart of the bargaining process. In other cases, the chief issue may be the quest for recognition by the state on the international stage, such as Libya but also Mauritania (since the coup d'état of August 2005).

The categories and key lines of argument used by European states and international agencies to conceptualize the migration issue and to justify their actions do not represent a homogeneous and hegemonic discourse. The agents in charge of implementing these policies have tended to draw the relevant elements from their discursive repertoire to suit the requirements of a specific national and local context, giving actors (i.e. states, civil society, associations, economic operators) the freedom to reinterpret them on the basis of endogenous social logics and issues.

Because of its reputation as a country without a "legal culture", the externalization of illegal migration control in Mauritania was immediately accompanied by a legal debate centring on the necessity of border control (rights of entry and exit) and the protection of vulnerable groups (Human Rights) 12 . The legal lexicon provides a code used by the entire range of actors concerned at some level with illegal migration to account for the practices governed by different (even conflicting) logics: pressures aimed at the elaboration of migration legislation tallying with the "instruments of migration management" by international agencies; the constitution of a civil society which (beyond the matter of immigration) fights for the creation of a democratic civil society in Mauritania that is respectful of human rights; the development of a sector devoted to training and awareness programmes for the "rights of migrants" offering new opportunities to a small proportion of qualified nationals; and the creation of labor legislation to monitor labor sectors and the distribution of jobs by areas of economic activity.

A comparison (however superficial) with other contexts shows how this policy has tended to focus on different types of action. For example in Dakar (see Pian), the focus on dissuasion campaigns, which is almost completely absent in Nouadhibou 13 , produces other opportunities and specific strategies for the appropriation of resources : the deportee associations aim to promote the experience of adventure as an expert skill that can be negotiated on the market of illegal migration management (i.e. "We know").

Finally, the conditions governing the implementation of these policies in Nouadhibou and the reorientations or emphases to which they are subject clearly depend on relations forged between the immigrants and local native populations in the history of the town and the changes linked to urban development.

It might therefore be argued that it is precisely the flexibility of the normative framework in which the problems and solutions of illegal migration are articulated that determines the unique efficiency of control policies. The articulation of the general discourse around a small number of loosely connected themes (co-development, dissuasion, the fight against trafficking, good governance) gives a marked degree of lability to the programmes designed to implement them. The result is the emergence of working misunderstandings in context adapted to every specific case: by embedding discursive categories of the globalized repertoire of migration management (transit, illegals) in local practices and issues, the case of 12 The authors of an IOM document on Mauritania's migration profile bemoaned "the general lack of recognition at a regional level of texts relating to the right of entry and exit and to residence permits for foreign nationals, as well as texts concerning the protection of vulnerable categories, including refugees, victims of human trafficking, unaccompanied children, etc". 13 Note however that a Mauritanian Association for the Fight against Illegal Immigration was created recently in Nouakchott by members of "civil society". Its purpose is to carry out campaigns aimed at raising awareness of the dangers of illegal migration (Mohammed-Saleh 2008).

  So if you need a servant, you phone the representative. Say I need a woman or a man for such and such a job. You go to see the representative, you tell him what you need and he gets you the person you need. It's just these kinds of practices that we're actively promoting. (APEAH President)

The reason for putting the phrase 'migration routes' in inverted commas is that the notion (and the status it assigns to specific areas or places) is an integral part of the discursive apparatus underlying the unification and legitimization of European migration policies.

Note however that the Black-African component of Mauritania's population has a long history of emigration to France.

Mauritania has been far more reluctant on this point. Two bills have nevertheless been submitted to the ministerial cabinet relating to entry and residence permits and to the right of asylum.

A transit situation is a situation in which individuals feel psychologically blocked wherever they may be.

The term is used in roughly the same sense as Bourdieu's use of the term 'realize' in speaking of the category of "family": the principle of the construction of a collective reality which sustains a social fiction as a reality insofar as it is collectively recognized[START_REF] Bourdieu Pierre | A propos de la famille comme catégorie réalisée[END_REF].

In other words, migrants who are not necessarily illegal in Mauritania but are presumed to be illegal on the basis of the intention that is ascribed to them, or in the case of migrants who are refused entry, the status of illegal migrant which would have been assigned to them elsewhere if they had been successful in their effort to migrate beyond Mauritania.

The currency of Mauritania.

Based on first-hand accounts collected during a period of research spent in Nouadhibou in March 2007.

But also probably as a result of the moratorium on fishing, which makes it impossible for pirogues to pass unnoticed among fishing boats.

This account and all subsequent quotes were collected during a period of research in Nouadhibou in July 2009.

Nouadhibou shows how the same categories can be viewed as predictive of the phenomena to which they refer because of such misunderstandings, and result in them becoming reality.