Yuqi Liu

Matteo D'achille

Universality in the one-dimensional Euclidean random assignment problem Étudiante

Cette thèse est composée de quatre chapitres thématiques. Le premier chapitre commence par rappeler quelques notions élémentaires de la théorie des graphes et introduit le problème général d'assignation aléatoire euclidienne. Le deuxième chapitre est une revue de littérature, centrée sur la dimension 1. Le troisième chapitre est consacré à l'étude d'un nouveau problème d'assignation aléatoire euclidienne "unidimensionnel". Le dernier chapitre 4 présente quelques perspectives pour les recherches futures.

Introduction

The theory of graphs came into existence during the first half of the 18th century with Euler publishing the paper on the Seven Bridges of Königsberg [START_REF] Biggs | Graph Theory, 1736-1936[END_REF]. This theory is particularly useful in dealing with combinatorial optimization problems, and in particular in the study of linear assignment problems. Thus, before explaining our problem, it is necessary to recall some definitions about graphs.

The reference for Subsection 1.1 is Chartrand et al. [START_REF] Chartrand | A first course in graph theory[END_REF].

Fundamentals of simple graph

A simple graph is a graph, without loops or parallel edges, in which every edge is undirected. A simple graph G consists of a finite nonempty set V (G) of objects called vertices and a set E(G) of 2-element subsets of V (G) called edges. If v 1 v 2 is an edge of G, then vertices v 1 and v 2 are said to be adjacent in G. The number of vertices and edges in G are called the order and size of G, and denoted by n(G) and m(G), respectively. The degree of a vertex v in a graph G is the number of edges incident with v and is denoted by deg G v.

Theorem. (The handshake lemma) If G is a simple graph of size m, then

v∈V (G) deg G v = 2m.
A graph G is a bipartite graph if V (G) can be partitioned into two subsets U and W , called partite sets, such that every edge of G joins a vertex of U and a vertex of W . We call G a complete bipartite graph if every vertex of U is adjacent to every vertex of W . A complete bipartite graph with n(U ) = s and n(W ) = t is denoted by K s,t or K t,s , so that its order is s + t and its size is s × t.

A collection of adjacent vertices that repeats no vertex (circuit), except for the first and last, is a cycle. A k-cycle is a cycle of length k. Graph K 5,3 and 6-cycle are shown in Figure 1

a ij =    1 if v i v j ∈ E(G) 0 otherwise, while the incidence matrix of G is the n × m matrix B = (b ij ), where b ij =    1 if v i is incident with e j 0 otherwise. We say that G ′ = (V, E ′ ) is a spanning subgraph or a factor of G = (V, E) if E ′ ⊂ E. If every
vertex of a factor has degree r then we call it an r-factor. A matching in K n,n is an 1-factor of K n,n .

If a simple graph G has no cycles, it is called acyclic or a forest. A tree is an acyclic connected simple graph. The size of a tree of order n is n -1.

The linear assignment problem

Let us now consider a combinatorial optimization problem, which is called "the assignment problem", and formulate it in the language developed in the previous section. (Appendix A provides a brief overview of combinatorial optimization.) In a complete bipartite graph K n,n with partite sets 1.3) and R = {r 1 , r 2 , ..., r n } (red dots in Figure 1.3), given a positive valued 1 cost function f defined on the edges, f : E → R + , we want to find a matching T = (V, E ′ ) of G for which the objective function

B = {b 1 , b 2 , ..., b n } (blue dots in Figure
f (T ) = 1⩽i,j⩽n a ij f (b i r j ) = bir π(i) ∈E ′ f (b i r π(i) )
is minimal. In this linear programming problem (see Appendix A), (a ij ) n×n is the adjacency matrix of T . The set of possible matchings is in bi-jection with the symmetric group S n , i.e. the group of all permutations of a set with n elements. The number of possible matchings is n 1 There is no loss of generality in this assumption, as a lower-bounded cost function f is enough for our scopes.

!. b 1 b 2 b 3 . . . b n r 1 r 2 r 3 . . . r n Figure 1.3: Graph K n,n b 1 b 2 b 3 . . . b n r 1 r 2 r 3 . . . r n Figure 1.4: A matching of K n,n

The Euclidean Random Assignment Problem

Turning now to formulate the d-dimensional Euclidean Random Assignment Problem (or "ERAP" for brevity) following the discussion in [START_REF] Matteo | Statistical Properties of the Euclidean Random Assignment Problem[END_REF]. This problem was first articulated in statistical mechanics by Mézard and Parisi as a prototypical model of finite-dimensional spin glass [START_REF] Mézard | The euclidean matching problem[END_REF].

In statistical mechanics, a primary concern are the typical properties of a system composed of many particles in the limit of low temperature. As the temperature is lowered the Boltzmann distribution (also called Gibbs distribution) collapses into the lowest energy state, which would dominate the properties of matter [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF].

Let us expand a bit on this remark with the following observations. Consider a statistical mechanical system with energies {E 1 , . . . , E n } in bijection with the microscopic configurations. The canonical partition function of the system [START_REF] Landau | Physique Théorique[END_REF][START_REF] Edwin | Information theory and statistical mechanics[END_REF] at inverse temperature β is

Z n (β) = n i=1 e -βEi ,
and the associated free energy is

f n (β) = - 1 β log Z n (β).
Since e max(-βE1,-βE2,...,-βEn) ⩽ n i=1 e -βEi ⩽ ne max(-βE1,-βE2,...,-βEn) , on taking logs we obtain max(-βE 1 , -βE 2 , . . . ,

-βE n ) ⩽ log n i=1 e -βEi ⩽ max(-βE 1 , -βE 2 , . . . , -βE n ) + logn, - 1 β max(-βE 1 , -βE 2 , . . . , -βE n ) ⩾ - 1 β log n i=1 e -βEi ⩾ - 1 β max(-βE 1 , -βE 2 , . . . , -βE n ) - 1 β logn. Indeed, - 1 β max(-βE 1 , -βE 2 , . . . , -βE n ) = min(E 1 , E 2 , . . . , E n ), lim β→+∞ 1 β logn = 0.
Then, we have

lim β→+∞ f n (β) = lim β→+∞ - 1 β log n i=1 e -βEi = min(E 1 , E 2 , . . . , E n ). (1)
Therefore, one could hope to use the properties of the ground state energy at zero temperature (left side of equation ( 1)) depending on some choices of disorder to understand the properties of the solution of the stochastic version of a combinatorial optimization problem (in which E 1 , E 2 , . . . , E n represent the possible values taken by the objective function of interest).

The ferromagnetic bonds and the antiferromagnetic bonds in a spin glass are sampled from an instance of a disorder distribution related to distances among "atoms" or "impurities" [START_REF] Mézard | Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications[END_REF], which are represented here by B and R. In particular, they are represented by points in a d-dimensional metric space (Ω, D). The statistical ensemble for the disorder distribution is denoted by (v B , v R ). Playing the role of energy, the cost function is restricted to a power function with an exponent p:

f (b i r π(i) ) = D p (b i , r π(i) ),
in order to share basic requirements for a physical system at criticality. For 2n = n + n points, we get

a n × n assignment cost matrix c =        D p (b 1 , r 1 ) D p (b 1 , r 2 ) . . . D p (b 1 , r n ) D p (b 2 , r 1 ) D p (b 2 , r 2 ) . . . D p (b 2 , r n ) . . . . . . . . . . . . D p (b n , r 1 ) D p (b n , r 2 ) . . . D p (b n , r n )        ,
and n! permutation matrices P π , with P i,j = δ j,π(i) .

Here, D(b i , r j ) is almost exclusively d-dimensional Euclidean distance of two vertices. But other choices for the metric D are possible.

A specific ERAP, built into this system, is completely specified by the triple

((Ω, D), (v B , v R ), p).
The energy (Hamiltonian) of a configuration π is

H (p) (π) = n i=1 D p (b i , r π(i) ) = Tr[P π c].
Then we will consider the optimal assignment π opt and the optimal cost

H (p) opt := H (p) (π opt ) = min π∈Sn H (p) (π).
The remaining part of this memoir will focus mostly on one-dimensional Euclidean random assignment problem, which means that B and R are distributed in a 1-dimensional metric space.

The link with Monge-Kantorovich problem

The relationship between two problems that both play an important role in optimal transport theory: the Euclidean random assignment problem and the Monge-Kantorovich problem, has already been explored. Brezis [START_REF] Brezis | Remarks on the monge-kantorovich problem in the discrete setting[END_REF] has recently remarked that what we call H opt in the discrete setting of ERAP is proportional to the so-called Wasserstein distance among the empirical distributions associated to Blue and Red points in the continuous setting of Monge-Kantorovich problem. Thus, when we discuss universality in the one dimensional ERAP, we can refer to the conclusions in Monge-Kantorovich problem, and some remarakable connections emerge. For example, the transport field in the one dimensional ERAP on the unit interval for p ≥ 1 has the Brownian bridge as a scaling limit [START_REF] Pitman | A guide to brownian motion and related stochastic processes[END_REF].

Vershik et al. [START_REF] Vershik | Kantorovich metric: Initial history and little-known applications[END_REF] have reminded of the history of the Wasserstein distance and the Monge-Kantorovich problem, and the remarkable role of them in linear programming. Recall that the Wasserstein transport distance W p (µ n , µ), p ⩾ 1, between µ n and µ is defined by

W p p (µ n , µ) = inf π R R d(x -y) p dπ(x, y) = E H (p) opt n .
This definition in [START_REF] Villani | Optimal transport: old and new[END_REF] indicates the link between W p (µ n , µ) and

H (p)
opt .

Literature review

This chapter is subdivided into two sections according to the value of the energy-distance exponent p. We will recall some results for the case p > 1, which will be useful in the next chapter. Then we will briefly mention the previous studies for the case 0 < p < 1 (concave regime) and the latest result for the borderline case p = 1.

Case p > 1

On the configuration π opt

Let the two sets of points be labeled in increasing order according to their position along the line.

The following property of the optimal matching has been reported in previous studies [START_REF] Boniolo | Correlation function for the grid-poisson euclidean matching on a line and on a circle[END_REF][START_REF] Caracciolo | Random euclidean matching problems in one dimension[END_REF].

Proposition 1. For p > 1, H (p) opt = H (p) (π),
if and only if

π(i) = i for all 1 ⩽ i ⩽ n.
Proof. Let the positions of any two red dots r i , r j and any two blue dots b i , b j be x 1 , x 1 + x 2 , y 1 ,

y 1 + y 2 , respectively. If 1 ⩽ i < j ⩽ n, we have x 2 ⩾ 0 and y 2 ⩾ 0. b i b j y 1 y 2 r i r j x 1 x 2
Depending on the permutations of b i and b j , there are two different costs:

1 2 . . . i . . . j . . . n -1 n π(1) π(2) . . . i . . . j . . . π(n -1) π(n) : H (p) 1 = |x 1 -y 1 | p + |x 1 + x 2 -y 1 -y 2 | p + C, 1 2 . . . i . . . j . . . n -1 n π(1) π(2) . . . j . . . i . . . π(n -1) π(n) : H (p) 2 = |y 1 + y 2 -x 1 | p + |x 1 + x 2 -y 1 | p + C.
We need to prove that

|d -y 2 | p + |d + x 2 | p ⩾ |d| p + |d + x 2 -y 2 | p , with d = x 1 -y 1 . For p > 1, convexity of f (x) = |x| p gives f (d + x 2 ) -f (d) > f (d + x 2 -y 2 ) -f (d -y 2 ).
This completes the proof.

ERAP and Brownian bridge

Let {b i , 1 ⩽ i ⩽ n} and {r i , 1 ⩽ i ⩽ n} be 2n uniform i.i.d. random variables on the interval [0, 1]. For n → +∞, a link between the ERAP and the Brownian bridge has been shown using Donsker's theorem [START_REF] Monroe | Justification and extension of doob's heuristic approach to the kolmogorovsmirnov theorems[END_REF].

Theorem. (Donsker's) Let {x i , i = 1, . . . , n} be n independent observations sampled from a distribution function F (x), and let F n (x) be the empirical cumulative function

F n (x) := 1 n {#x i |x i < x}.
Then, as n → +∞, √ n(F n (x) -F (x)) converges in distribution to the Brownian Bridge B br x .

The standard Brownian Bridge B br x is a centered Gaussian process with covariance E(B br t B br s ) = t(1 -s) when 0 ⩽ t ⩽ s ⩽ 1 (see [START_REF] Pitman | A guide to brownian motion and related stochastic processes[END_REF] for a review and [START_REF] Werner | Lecture notes on the gaussian free field[END_REF] for remarks on the relevance of the Brownian Bridge in one dimensional stochastic models).

The idea of a Grid-Poisson ERAP was first proposed in [START_REF] Boniolo | Correlation function for the grid-poisson euclidean matching on a line and on a circle[END_REF] [START_REF] Boniolo | Correlation function for the grid-poisson euclidean matching on a line and on a circle[END_REF] and Caracciolo et al. (2014) [START_REF] Caracciolo | One-dimensional euclidean matching problem: exact solutions, correlation functions, and universality[END_REF]. In this problem, B, replaced by P grid , is a deterministic grid on the domain Λ n rather than a set of independent random variables. A common choice has been the uniform grid:

P grid = {p grid i |p grid i = i n + 1 , 1 ⩽ i ⩽ n}.
From Donsker's theorem, we have (see Denoting by

φ i := b i -r i , for all 1 ⩽ i ⩽ n,
the authors of Refs. [START_REF] Caracciolo | Random euclidean matching problems in one dimension[END_REF] have presented that (see

Figure B.1(3)) ϕ(s) := √ nφ ns+ 1 2 n→+∞ ----→ B br (s; ω) -B br (s; ω),
here, s is a new variable such that i = ns + 1 2 , B br (s; ω) and B br (s; ω) are independent. This has allowed the computation of some statistical properties of the minimal energy. For example, at p = 2, we have

lim n→+∞ E H (2) opt = lim n→+∞ E H (2) (π opt ) = lim n→+∞ E n i=1 |φ i | 2 = E lim n→+∞ n i=1 |φ i | 2 = E 1 0 ϕ(s) 2 ds = E 1 0 (B br (s; ω) -B br (s; ω)) 2 ds = E 1 0 (B br (s; ω)) 2 ds + E 1 0 (B br (s; ω)) 2 ds = 2 1 0 s(1 -s)ds = 2 s 2 2 - s 3 3 1 0 = 1 3 ,
(a similar computation holds for any p > 1). More recently, due to the an exact rewriting of E[H

(p)
opt ] in terms of a Generalized Selberg Integrals [START_REF] Caracciolo | Selberg integrals in 1d random euclidean optimization problems[END_REF], it has been shown that there exists an exact formula valid ∀n, and ∀p ⩾ 1, E[H

(p) opt ] = n Γ(1 + p/2)Γ(n + 1) (p + 1)Γ(n + 1 + p/2) ,
where Γ is Euler's function.

Case 0 < p ⩽ 1

Whilst this case has received much less attention than the case p > 1, it did have several practical applications in economic terms. Imagine being in a railway line or highway, the concavity of the cost function can reflect a shipping tariff that increases with the distance, even while the cost per mile shipped goes down. McCann [START_REF] Robert | Exact solutions to the transportation problem on the line[END_REF] has introduced the application model and the following proposition.

Proposition 2. (No-crossing rule)

For 0 < p < 1, π opt has no crossing.

Figure 2.1: No-crossing rule

There is usually more than one assignment that satisfies the non-crossing property, so this property is not sufficient to fully characterize the optimal assignment. Recently, a specific matching rule, giving a canonical but sub-optimal configuration, the Dyck matching, has been proposed [START_REF] Caracciolo | The dyck bound in the concave 1-dimensional random assignment model[END_REF]. On the basis of extensive numerical evidences, it has been conjectured that the expected energy of Dyck matchings has the same leading asymptotics of the unknown optimal matching, up to constants in n [START_REF] Caracciolo | The dyck bound in the concave 1-dimensional random assignment model[END_REF].

The case p = 1 has also attracted some interest recently [START_REF] Caracciolo | The number of optimal matchings for euclidean assignment on the line[END_REF], as it is degenerate. As the cost function changes concavity at p = 1, there are at least two distinct optimal matchings for each instance, the ordered matching and the Dyck matching. It is atypical for these two situations to coincide.

For the transportation problem, the case of the line segment is idealized, and in the next chapter we investigate how these conclusions can be extended to a crossroads.

|v (1) 1 -v (1) 2 | D(v 1 , v 2 ) = |v (1) 1 -v (1) 2 | v (1) 2 v (1) 1 D(v 1 , v 2 ) = v (1)
1 + v

(1) 2

Figure 3.3: Distance between two dots

Step 1.

Suppose there are m α b blue dots and m α r red dots with direction2 α, they are :

• {b i = (b (1) i , α) : b (1) i ⩾ b (1) j , 1 ⩽ i ⩽ j ⩽ m α b ⩽ n} and • {r i = (r (1) i , α) : r (1) i ⩾ r (1) j , 1 ⩽ i ⩽ j ⩽ m α r ⩽ n}.
For the m α (= min(m α r , m α b )) pairs of data, we define H (p) α (π), which is a part of H (p) (π), as follows:

H (p) α (π) = m α i=1 D p (b i , r π(i) ), for all p ⩾ 1,
and the corresponding optimal cost

H (p) α,opt = min π∈S m α H (p) α (π), for all p ⩾ 1.
According to Proposition 1, for p ⩾ 1, if we neglect the remaining points,

H (p) α,opt = H (p) α (π),
if and only if

π(i) = i for all 1 ⩽ i ⩽ m α .
For the convenience of follow-up discussion, we delete the labels of some dots: {b i , r i : i > m α }.

Step 2.

In the same way, we suppose there are m β b blue dots and m β r red dots with direction β, they are :

• {b i = (b (1) i , β) : b (1) i ⩾ b (1) j , m α < i ⩽ j ⩽ m α + m β b ⩽ n} and • {r i = (r (1) i , β) : r (1) i ⩾ r (1) j , m α < i ⩽ j ⩽ m α + m β r ⩽ n}.
After defining m β = min(m β r , m β b ), we delete the labels of some dots: {b i , r i : i > m α + m β }. Similarly, we label m γ b blue dots and m γ r red dots with direction γ:

• {b i = (b (1) i , γ) : b (1) i ⩾ b (1) j , m α + m β < i ⩽ j ⩽ m α + m β + m γ b ⩽ n} and • {r i = (r (1)
i , γ) : r

(1) i ⩾ r (1) j , m α + m β < i ⩽ j ⩽ m α + m β + m γ r ⩽ n}.
Then, we define m γ = min(m γ r , m γ b ), and delete the labels of some dots:

{b i , r i : i > m α +m β +m γ }. For all p ⩾ 1, H (p) β (π), H (p) γ (π), H (p) β,opt and H (p)
γ,opt are defined as follows:

H (p) β (π) = m α +m β i=m α +1 D p (b i , r π(i) ), H (p) α (π) = m α +m β +m γ i=m α +m β +1 D p (b i , r π(i) ), H (p) β,opt = min π∈S m β H (p) β (π), H (p) γ,opt = min π∈S m γ H (p) γ (π).
Likewise, according to Proposition 1, for p ⩾ 1,

H (p) β,opt = H (p) β (π), H (p) γ,opt = H (p) γ (π),
if and only if

π(i) = i for all m α + 1 ⩽ i ⩽ m α + m β + m γ .
An example of optimal solution in each direction is illustrated in Figure 3.4.

(1, α)

(1, β) (1, γ) b 1 r 1 b 2 r 2 r 3 b 3 r 4 b 4

Figure 3.4: Connection in each direction

In the first two steps, if we swap the order of α, β and γ, the result remains the same.

Step 3.

After the second step, there are m * blue dots and m * red dots left unlabelled. Here,

m * = n -(m α + m β + m γ ).
We label these 2m * dots as follows:

• {b i = (b (1)
i , b

(2)

i ) : b (1) i ⩾ b (1) j , m α + m β + m γ < i ⩽ j ⩽ n} and • {r i = (r (1)
i , r

(2)

i ) : r (1) i ⩽ r (1) j , m α + m β + m γ < i ⩽ j ⩽ n}.
For all p ⩾ 1, H * (p) (π) and H * (p) opt are defined as follows:

H * (p) (π) = n i=m α +m β +m γ +1 D p (b i , r π(i) ), H * (p) opt = min π∈S m * H * (p) (π).
H * (p) opt = H * (p) (π),
if and only if

π(i) = i for all m α + m β + m γ + 1 ⩽ i ⩽ n. b 1 r 2 r 1 b 2 (1, α) (1, β) r 2 b 1 b 2 r 1 (1, α) (1, β) (1, γ) r 2 b 1 b 2 r 1 (1, α) (1, β) (1, γ) Figure 3
.5: The optimal cost is the same in these three cases

In summary, we have defined a matching rule in a canonical way which proceeds through sorting of blue dots and red dots on the branches ("pruning of the tree"), and then deals with the remaining points in a unique way. Clearly, this rule generically returns a sub-optimal configuration. The cost of this rule is denoted by

H (p) prune , i.e. H (p) prune = H (p) α,opt + H (p) β,opt + H (p) γ,opt + H * (p) opt .

Conclusions

The following conclusions can be drawn from our numerical results: In summary, we can formulate the following conjecture: Conjecture 1. The expected ground state energy at p = 2 is asymptotically

lim n→+∞ E H (2) opt = 3k -2 3k 2 .
The validity of equation ( 2) is conforted by the numerical results reported in Figure B.7. Assuming the preceding conclusions, we can get the limits by computing the variance of the standard Brownian bridge stopped at time 1/k as follows:

lim n→+∞ E H (2) opt = lim n→+∞ E H (2) prune = lim n→+∞ E( n-m * i=1 |φ i | 2 ) = k lim αj →+∞ E m α j i=1 |φ i | 2 = k E lim αj →+∞ m α j i=1 |φ i | 2 = k E 1 k 0 ϕ(s) 2 ds = k E 1 k 0 (B br (s; ω) -B br (s; ω)) 2 ds = k E 1 k 0 (B br (s; ω)) 2 ds + kE 1 k 0 (B br (s; ω)) 2 ds = 2k 1 k 0 (s(1 -s))ds = 2k s 2 2 - s 3 3
1 k 0 = 3k -2 3k 2 . ( 2
)

Research perspectives

In the previous chapter we have started to study some of the properties on the case of the line segment to crossroads with k branches. Several questions still remain to be answered. Finally, the issue of the extension of this problem into higher dimensions is an intriguing one which could be usefully explored in further research. Here we propose two constructions:

• the points of both colors are uniformly distributed on a regular polygon of area 1 with k sides, the circumradii are impassable radii so that matchings among different elementary triangles are realised via the barycenter (see Figure 4.2);

• the points of both colors are uniformly distributed on k semicircles, the diameters of which all coincide (see Figure 4.3).

Due to time constraints, the number of simulated instances in this memoir were only 1000 or 500.

Although for one-dimensional problems we started to see a way towards possible reductions in computational complexity (and hence much faster algorithms and statistical power), in higher dimensions a larger number of simulations may be required.

A Combinatorial optimization

This appendix gives a brief review of combinatorial optimization (see [START_REF] Leslie R Foulds | Combinatorial optimization for undergraduates[END_REF] for an introductory textbook). Combinatorial optimization concerns problems for which the number of possible solutions is finite and often large. The following is a brief description of the general minimization problem of combinatorial optimization. Having introduced what is meant by combinatorial optimization, it is now necessary to move on to discuss some tools for studying these problems.

Since S is finite, we could theoretically solve the general minimization problem with simply exhaustive enumeration as follows:

Evaluate f (x) for all x ∈ S, compare all the function values and choose the smallest.

For many realistic problems the set S have many elements, and it is obvious that the usefulness of enumeration is limited by the size of S. Consequently, different methods have been proposed. For example, the transportation problem can be solved by the stepping-stone method.

The linear programming plays a key role in addressing the issue of combinatorial optimization.

We can formulate the linear programming problem in terms of matrices as Max CX subject to AX ⩽ b, and X ⩾ 0.

  .1 and Figure 1.2.

7 Figure 1 . 1 : 6 Figure 1 . 2 : 6 -cycle C 6 2 A

 711612662 Figure 1.1: Complete bipartite graph K 5,3

Figure B. 1 ( 1 )

 11 for a pictorial representation) √ n(p grid i -r i ) n→+∞ ----→ B br (s; ω). In the same way, (shown in Figure B.1(2)) √ n(b i -p grid i ) n→+∞ ----→ -B br (s; ω).

Figure 3 .

 3 Figure 3.5 illustrates that, according to Proposition 1, for p ⩾ 1,

1 . 2 ) opt and H ( 2 ) 2 ) 2 .

 12222 As shown in Figure B.2, we can plot the ratio of the optimal solution 3 H (prune as a function of n -0.5 . And from the Figure B.3 we can see that the solution H (prune appears to be close to the optimal solution H The sum of costs of connection in different directions (i.e. H * (2) opt ) appears to tend to 0, when n → +∞ (see Figure B.4). 3. The ratio of the number of connections in each direction to all (i.e. m α i n ) tend to 1 k , when n → +∞ (see Figure B.5). 4. For the connections in each direction, the distances are related to the Brownian motion (see Figure B.6), that is similar to the conclusion in the section 2.1.2.

Firstly, for equation ( 2 ) 3 )Figure 4 . 1 :

 2341 Figure 4.1: Inspiration from π prune to π opt

Figure 4 . 2 :Figure 4 . 3 :

 4243 Figure 4.2: Points distributed on a regular pentagon of area 1

  Let f : D → R be a real-valued function with domain D. Let S ⊆ D be the set of possible solutions, x ∈ S is called a feasible solution. The purpose of the general minimization problem of combinatorial optimization is to find x * ∈ S such thatf (x * ) ⩽ f (x) for all x ∈ S.The definition of the general maximization problem of combinatorial optimization is analogous.Typical combinatorial optimization problems are the travelling salesman problem, the transportation problem, the vehicle scheduling problem.

C

  = (c 1 , c 2 , ..., c n ), X =

Figure B. 5 :

 5 Figure B.5: The ratio of the number of connections in each direction to all when k is 3. The number of simulated instances is 500.

Figure B. 6 :

 6 Figure B.6: Optimal transport field on each direction with n = 1000 and k = 3.

Figure B. 7 :

 7 Figure B.7: Comparison between the numerical results and the results of equation (2). "LSLR" means "Least Squares Linear Regression". The number of simulated instances is 1000.

Figure B. 8 :

 8 Figure B.8: E n [ m * n ] as a function of 1/ √ n with an SEM error bars. The number of simulated instances is 1000.

Figure B. 9 :

 9 Figure B.9: E n [r max ] as a function of 1/ √ n with an SEM error bars. The number of simulated instances is 1000.

For simplicity, we replace {α 1 , α 2 , α

} with {α, β, γ}.

We obtained the optimal result in Python with the help of the Jonker-Volgenant algorithm[START_REF] Jonker | A shortest augmenting path algorithm for dense and sparse linear assignment problems[END_REF], a primal-dual algorithm based on the celebrated Hungarian algorithm by Kuhn[START_REF] Harold W Kuhn | The hungarian method for the assignment problem[END_REF]. The time complexity of the Jonker-Volgenant algorithm is O(n 3 ).

A 1-dimensional Euclidean random assignment problem 3.1 Hypothesis

We begin with presenting the triple ((Ω, D), (v B , v R ), p) in this "one-dimensional" ERAP.

A labeled tree G * with k edges is illustrated in Figure 3.1, k is a positive integer. n blue dots {b i , 1 ⩽ i ⩽ n} and n red dots {r i , 1 ⩽ i ⩽ n} are distributed in these k edges according to the following law:

• For a dot v, the distance from center is denoted by v (1) , and follows a continuous uniform variable on the interval [0, 1 k ]: v (1) ∼ U (0, 1 k );

• For a dot v, the direction (i.e. the edge which a dot is on) is denoted by v (2) , and follows a discrete

• The dot v is labeled as (v (1) , v (2) ).

For k = 3, a realization of 2 blue dots {b 1 , b 2 } and 2 red rods {r 1 , r 2 } is illustrated in Figure 3.2.

2 ), the distance (see Figure 3.3) between them is defined as following:

2 , i.e. they are in the same direction, v

2 , i.e. they are not in the same direction.

We will consider the case p ⩾ 1 in the section 3.2, and the case p = 2 in the section 3.3.

On the configuration π prune

Inspired by the work of Boniolo et al. [START_REF] Boniolo | Correlation function for the grid-poisson euclidean matching on a line and on a circle[END_REF] and of Caracciolo et al. [START_REF] Caracciolo | The dyck bound in the concave 1-dimensional random assignment model[END_REF], we will introduce a suboptimal configuration, which is called π prune . On this configuration, we are able to build a unique solution of H (p) , then show in the next section that this solution is close to the optimal solution. The following steps will be exemplified for the case k = 3 but generalize simply to other values of k.

B Supplementary figures


PharmD Marion Laureau

MD Olivier Vuillot

MD Vincent Gourhant

MD Damien Perier

MD Véronique Pinzani

PharmD Laura Lohan

PharmD Marie Faucanie

MSc Valérie Macioce

PhD, § Grégory Marin

MD,|| Isabelle Giraud

PharmD Anne Jalabert

PharmD Maxime Villiet

PharmD Audrey Castet-Nicolas

MD Mustapha Sebbane

PhD, † Cyril Breuker
email: c-breuker@chu-montpellier.fr

Adverse Drug Events Detected by Clinical Pharmacists in an Emergency Department : A Prospective Monocentric Observational Study

Keywords: emergency department, adverse drug event, clinical pharmacist, medication history

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

The Institute of Medicine defined an adverse drug event (ADE) has "any injury resulting from medical intervention related to a drug." This definition includes harm caused by the drug and harm from the use of the drug. [START_REF] Nebeker | Clarifying adverse drug events: a clinician's guide to terminology, documentation, and reporting[END_REF] Adverse drug events occur in 2% to 22% of inpatients [START_REF] Martins | Adverse drug events among adult inpatients: a metaanalysis of observational studies[END_REF] and in 5% to 35% of outpatients. [START_REF] Tache | Prevalence of adverse drug events in ambulatory care: a systematic review[END_REF] Moreover, between 10% and 19% of visits to an emergency department (ED) are related to an ADE. [START_REF] Queneau | et alAssociation Pédagogique Nationale pour l'Enseignement de la Thérapeutique (APNET). Emergency department visits caused by adverse drug events: results of a French survey[END_REF][START_REF] Budnitz | Medication use leading to emergency department visits for adverse drug events in older adults[END_REF][START_REF] Roulet | Implementing a clinical pharmacy survey of adverse drug events in a French emergency department[END_REF] Adverse drug events are major public health issues in hospitals because of their high morbidity/mortality and economic costs. [START_REF] Hohl | Outcomes of emergency department patients presenting with adverse drug events[END_REF][START_REF] Khan | Comparative epidemiology of hospital-acquired adverse drug reactions in adults and children and their impact on cost and hospital stay-a systematic review[END_REF] For instance, a study on the injectable medication error burden in the United States showed that half of ADEs are preventable because these are caused by medication errors and that ADEs affect more than 7 million patients, cause 7000 deaths, and cost more than U.S. $21 billion in direct medical costs annually. [START_REF] Lahue | National burden of preventable adverse drug events associated with inpatient injectable medications: healthcare and medical professional liability costs[END_REF] In the general population and in specific categories, such as elderly people, causes of drug-related hospital admissions/ED visits include polypharmacy, polyphysicians, noncompliance, medication errors, and inappropriate prescriptions. [START_REF] Nivya | Systemic review on drug related hospital admissions -a pubmed based search[END_REF][START_REF] Patel | Drug-related visits to the emergency department: how big is the problem?[END_REF][START_REF] Jolivot | A systematic review of adult admissions to ICUs related to adverse drug events[END_REF] Adverse drug event detection, documentation, and reporting are essential for adequate medical care and to improve the knowledge on the risk/benefit profiles of medications throughout their lifecycle. However, in the clinical practice, ADE underreporting is a generalized and widespread problem, [START_REF] Stergiopoulos | A survey of adverse event reporting practices among US healthcare professionals[END_REF][START_REF] Hazell | Under-reporting of adverse drug reactions: a systematic review[END_REF] with up to 93% of identified ADEs without relevant internal occurrence report. [START_REF] Howe | A review of the Office of Inspector General's reports on adverse event identification and reporting[END_REF] The main reasons for underreporting are difficulties in determining the ADE cause, lack of time, poor integration of ADE-reporting systems, uncertainty about the reporting procedures, and lack of immediate clinical interest by the clinicians. [START_REF] Stergiopoulos | A survey of adverse event reporting practices among US healthcare professionals[END_REF][START_REF] Hohl | Can reporting of adverse drug reactions create safer systems while improving health data?[END_REF] Rapid ADE detection is also crucial because its successful treatment depends on the ability of physicians to attribute the symptoms to a medication. However, ADE detection by ED physicians is often suboptimal, [START_REF] Hohl | Emergency physician recognition of adverse drugrelated events in elder patients presenting to an emergency department[END_REF][START_REF] Hohl | Do emergency physicians attribute drug-related emergency department visits to medication-related problems?[END_REF] particularly because of the unavailability or poor accuracy of the patients' medication history. [START_REF] Roulet | Assessment of adverse drug event recognition by emergency physicians in a French teaching hospital[END_REF] Indeed, up to two third of medication histories contain at least one error. [START_REF] Tam | Frequency, type and clinical importance of medication history errors at admission to hospital: a systematic review[END_REF] Several studies suggest that among healthcare providers, pharmacists and student pharmacists might be better suited to obtain detailed medication history [START_REF] Mergenhagen | Pharmacist-versus physician-initiated admission medication reconciliation: impact on adverse drug events[END_REF][START_REF] Mathys | Effect of pharmacy students as primary pharmacy members on inpatient interdisciplinary mental health teams[END_REF][START_REF] Lancaster | Impact of students pharmacists on the medication reconciliation process in high-risk hospitalized general medicine patients[END_REF] and to perform medication reconciliation, including in EDs. [START_REF] Mekonnen | Effectiveness of pharmacist-led medication reconciliation programmes on clinical outcomes at hospital transitions: a systematic review and meta-analysis[END_REF][START_REF] Mcnab | Systematic review and meta-analysis of the effectiveness of pharmacist-led medication reconciliation in the community after hospital discharge[END_REF] Therefore, a pharmacist team is routinely deployed in the ED of our hospital since November 2011 to help the ED team detect ADEs, particularly by collecting the patients' medication history. The primary objective of our study was to assess the rate and characteristics of ADEs identified by the pharmacist team in our ED. The secondary objective was to identify risk factors associated with ADEs and particularly with severe ADEs in ED patients. Indeed, a more detailed knowledge of ADE characteristics and risk factors may improve their detection by ED physicians.

unit. Patients who require longer surveillance are addressed to the short stay emergency hospitalization unit. Our study was performed according to the World Medical Association Declaration of Helsinki and was approved by the hospital institutional reviewboard. Oral consent was obtained from all participants or from a member of their family. This study was registered on ClinicalTrials.gov (NCT03442010). Only the authors involved in the patients' management had access to their nonanonymized medical data. Patient data were then anonymized by removing any identifying information before the analysis.

Participants

Participation in this study was proposed by clinical pharmacists to all adult patients (>18 y) admitted to the ED from November 2011 to April 2015 and who underwent a medication history interview (for medication reconciliation) with a member of the pharmacist team from 8:00 a.m to 6.00 p.m., Monday to Friday (Fig. 1, flow chart). Patients were prospectively and consecutively included and were followed until ED discharge. Patients were not included if they presented acute psychological troubles or if they (or a family member) refused to participate in the study or in the case of voluntary medication poisoning.

Interventions

The ED medical staff includes junior emergency physicians, a senior physician who supervises medical decisions, and a pharmacist team (one senior pharmacist, one resident, and four pharmacy students). The ED pharmacist team carries out as many medication history interviews as possible from 8:00 a.m. to 6:00 p.m. (Monday-Friday) according to the availability of the pharmacist team. Therefore, all the patients included in the study were interviewed during these working hours but could have arrived at the ED at any time. All pharmacist team members received specific training on ADE detection [START_REF] Arimone | Updating the French method for the causality assessment of adverse drug reactions[END_REF][START_REF] Trotti | CTCAE v3.0: development of a comprehensive grading system for the adverse effects of cancer treatment[END_REF][START_REF] Naranjo | A method for estimating the probability of adverse drug reactions[END_REF] and medication reconciliation, according to the High 5s project standard operating procedures. [START_REF] Van Den Bemt | Effect of medication reconciliation on unintentional medication discrepancies in acute hospital admissions of elderly adults: a multicenter study[END_REF][START_REF] Arimone | Update of the French drug reaction assessment method[END_REF] With each included patient, the pharmacist team carried out a structured interview to determine (a) the best possible medication history (BPMH), including self-medication and medication reconciliation and (b) the self-reported adherence as well as when and how they took their drug(s). The BPMH interview was conducted following the standard operating procedures recommended by the World Health Organization, [START_REF] Van Den Bemt | Effect of medication reconciliation on unintentional medication discrepancies in acute hospital admissions of elderly adults: a multicenter study[END_REF] as previously described. [START_REF] Breuker | Medication errors at hospital admission and discharge: risk factors and impact of medication reconciliation process to improve healthcare[END_REF] The BPMH was defined as the most comprehensive list of all medications taken by the patient, including prescription drugs and self-medication, and was obtained through the following: (a) the patient's interview (or family interview if the patient could not answer); (b) drug prescriptions, if available; (c) phone calls to community pharmacies, physicians, and/or nurses; and (d) electronic medical record. The BPMH was based on at least two sources of information.

The sociodemographic data, medical history, current clinical status, FRENCH triage scale level, and clinical out-come were also collected by the pharmacist team.

Outcomes and Measurements

The primary outcome was the ADE rate. Adverse drug event was defined as any harm caused by the use of a drug or the inappropriate use of a drug.1 This definition included injuries (signs, symptoms, or laboratory abnormalities) resulting from adverse drug reactions (ADRs) or noncompliance to medication prescriptions. Voluntary medication poisoning was excluded from the ADE definition. Adverse drug events were classified in two categories: "direct ADR" (when the medication was judged to be the only cause of the pathological condition) and "participating ADR" (when the medication was judged not to be the only cause of the pathological condition, but to have facilitated or aggravated it). [START_REF] Roulet | Assessment of adverse drug event recognition by emergency physicians in a French teaching hospital[END_REF] Adverse drug events were attributed to a medication by the pharmacist and confirmed by the treating senior ED physician, in real time. The medication causality was based on the search for chronological, semiological (symptoms, contributing factors, complementary exam results...), and bibliographic objective criteria. [START_REF] Arimone | Updating the French method for the causality assessment of adverse drug reactions[END_REF][START_REF] Naranjo | A method for estimating the probability of adverse drug reactions[END_REF] The ADE severity was assessed according to the Common Terminology Criteria for adverse events as spontaneous regression, regression after symptomatic treatment, hospitalization with no life-threat, life-threatening risk, and death. Severe ADEs were defined as ADEs that required hospitalization or led to the patient's death. [START_REF] Trotti | CTCAE v3.0: development of a comprehensive grading system for the adverse effects of cancer treatment[END_REF] In the case of doubt about the diagnosis or category of an ADE, the case was reviewed by an expert committee that included two senior ED physicians, one senior and one junior clinical pharmacists, and one pharmacovigilance physician. The medication causality was confirmed by consensus among the five members. Cases of medication toxicity were notified to the regional pharmacovigilance center at the physicians and pharmacists' discretion.

For each ADE, the medication involved as well as the ADE category (direct ADR, participating ADR, noncompliance to medication prescription), and severity were recorded.

Analysis

The patients' characteristics were described with percentages for categorical variables and means ± standard deviations for quantitative variables. The characteristics of patients with ADE and without ADE were compared with the Student t or the Mann-Whiney U test for continuous variables and with the χ2 or Fisher exact test for categorical variables. The variables considered as candidate ADE predictors included all data collected by the pharmacist team (e.g., patients' characteristics, demographic, reasons for ED visit, current medications…) and variables already reported in the literature as ADE risk factors (age, [START_REF] Pedros | Prevalence, risk factors and main features of adverse drug reactions leading to hospital admission[END_REF][START_REF] Alexopoulou | Adverse drug reactions as a cause of hospital admissions: a 6-month experience in a single center in Greece[END_REF][START_REF] Leendertse | Frequency of and risk factors for preventable medication-related hospital admissions in the Netherlands[END_REF][START_REF] Andreazza | Causes of drug-related problems in the emergency room of a hospital in southern Brazil[END_REF][START_REF] Alhawassi | A systematic review of the prevalence and risk factors for adverse drug reactions in the elderly in the acute care setting[END_REF][START_REF] Kongkaew | Risk factors for hospital admissions associated with adverse drug events[END_REF] sex, [START_REF] Pedros | Prevalence, risk factors and main features of adverse drug reactions leading to hospital admission[END_REF][START_REF] Fattinger | Epidemiology of drug exposure and adverse drug reactions in two Swiss departments of internal medicine[END_REF][START_REF] Becker | Sex differences in drug abuse[END_REF][START_REF] Van Etten | Male-female differences in transitions from first drug opportunity to first use: searching for subgroup variation by age, race, region, and urban status[END_REF][START_REF] Van Etten | Male-female differences in the earliest stages of drug involvement[END_REF][START_REF] Abegaz | Nonadherence to antihypertensive drugs: a systematic review and meta-analysis[END_REF] number of treatments, and some drug types,37,44 such as antineoplastic compounds). The association between variables and ADE risk was analyzed using logistic regression.

The variables with P values lower than 0.15 in univariate models were considered for multivariable analyses. After stepwise selection, only the variables with P values lower than 0.05 in the multivariable model were considered significantly associated with ADE risk and were kept in the final multivariable model. All the variables analyzed in the univariate models are represented in the tables that, however, only present the odds ratios of the variables included in the final multivariable model.

The risk factors of severe ADEs (hospitalization with no life threat, life-threatening risk, or death) versus spontaneous regression or regression after symptomatic treatment were also analyzed, using the same methodology. Missing data were not replaced. Statistical analyses were performed with SAS 9.1 (SAS Institute, France), and the statistical bilateral significance threshold was set at 5%.

RESULTS

Characteristics of the Study Population

Among the 140,953 patients who visited the ED from November 2011 to April 2015, 8275 patients (5.9%) were included in the study. The study population's baseline characteristics (at ED entry) are presented in Table 1. The mean ± SD age was 59.7 ± 22.9 years, and the sex ratio was close to 1; 68.8% of them arrived at the ED during working hours/days and 31.2% during the night or weekend.

Patients presented to the ED mainly for cardiovascular (23.8% of all included patients) and hepatogastrointestinal (22.1%) reasons. On average, they were taking 4.8 ± 4.2 drugs. In total, 3084 patients (38% of all included patients) were hospitalized after the passage at the ED, and 25 (0.3%) patients died at the ED. Moreover, 20.5% (633/3084) of hospitalizations and 52% (13/25) of deaths at the ED were related to an ADE. Adverse drug events were detected in 1299 patients (15.7% of the study population), with no difference between patients who entered the ED during working hours/days and during the night/weekend (15.8% versus 14.9%, P = 0.39). In comparison with the non-ADE population, the ADE population was older (65.8 ± 21.5 versus 58.5 ± 23.0 y), with a higher proportion of men (51.4% versus 47.7%), of patients living in institution (11.9% versus 7.5%), and number of taken drugs (6.3 ± 3.8 versus 4.5 ± 4.2) (Table 1). Moreover, the rates of death at the ED and hospitalization were higher in the ADE than in the non-ADE group (1% versus 0.2% and 49.3% versus 35.4%, respectively).

Description of ADEs Cases

The most frequent ADE-related symptoms were bleeding (24.7% of all ADEs), neurologic (17.0%), metabolic (14.5%), gastrointestinal (11.1%), and cardiovascular problems (8.9%). In total, 37.4% of ADEs were caused by direct medication effects ("direct ADR"), 23.6% by noncompliance with prescription (underuse or misuse), and 33.7% by the drug contribution to a multifactorial pathological condition ("participating ADR") (Table 2). Among patients with ADE, the ADE was the direct cause of the ED visit in 86.7% of cases (n = 1126/1299), and it led to hospitalization in 48.8% (633/1299) and to death in 2.2% (29/1299) (1.0% in ED and 1.2% during the post-ED hospitalization). Medications targeting the nervous system (482 of the 1689 drugs taken by patients with ADE, 28.5%), blood and blood-forming organs (396/1,689, 23.4%), cardiovascular system (239/1689, 14.2%), and alimentary tract and metabolism (208/1689, 12.3%) were more often involved in the detected ADEs (Table 3). On the other hand, ADEs were more frequent in patients who took antineoplastic and immunomodulating agents (20.7% of all patients treated with these drugs), medications for blood and blood-forming organs (10.4% of all patients treated with these drugs), and anti-infective drugs for systemic use (9.3% of all patients treated with these drugs) (Table 3).

Adverse Drug Event Risk Factors

The multivariable analyses showed that overall, ADEs were associated with male sex, ED visit for neurologic problems, visit to the emergency critical care unit or to the short stay hospitalization unit, use of blood and blood-forming agents, anti-infective drugs for systemic use, and antineoplastic/immunomodulating agents (Table 4). Moreover, each ADE category was associated with different variables. Specifically, male sex, alcohol consumption, and visit to the short stay hospitalization unit were associated with participating and noncompliance ADRs, but not with direct ADRs. On the other hand, visit to the emergency critical care unit and antineoplastic/immunomodulating medications were associated with direct and participating ADRs, but not with noncompliance ADRs. A number of drugs higher than 5 was associated only with direct ADRs.

Risk Factors of Severe ADEs

The results of the univariate and multivariable analyses for the risk of severe ADEs are presented in Table 5. In multivariable analyses, age, male sex, renal failure, visit to the emergency critical care unit or to the short stay hospitalization unit, and the use of blood and antineoplastic/immunomodulating medications and participating ADRs were associated with severe ADEs. Conversely, ED visit without immediate need of urgent care (FRENCH triage scale level 5) and ED visit for cardiovascular problems were associated with a lower risk of severe ADEs.

DISCUSSION

The rapid identification and treatment of ADEs are fundamental to improve the quality of care and therapeutic outcomes. In EDs, physicians need immediate and complete access to clinical and therapeutic information to diagnose ADEs and provide quality care. To this aim, physicians, pharmacists, and all healthcare professionals must work together to combine their respective expertise and resources. In our study, the clinical pharmacy team contributed to identify ADEs in 15.7% (1299/8275) of the patients who underwent a medication history interview during their visit to the ED. Moreover, our multivariable analysis highlighted some risk factors of ADE and severe ADE.

Previous studies have investigated ADE incidence and types in different healthcare settings, such as communities, community pharmacies, hospitals, and EDs. [START_REF] Basger | Application of drug-related problem (DRP) classification systems: a review of the literature[END_REF] However, comparisons are difficult because ADE definition differed among studies and sometimes overlapped with other terms, such as drug-related problems, drug related visit, or medication errors. Moreover, the methodologies used to assess ADE incidence often varied among works, which are either prospective studies including only a few hundreds of patients or retrospective cohort studies with several thousands of patients. Retrospective cohort studies are often based on National Health Service databases where ADEs are identified using a list of International Classification of Diseases codes. [START_REF] Hohl | ICD-10 codes used to identify adverse drug events in administrative data: a systematic review[END_REF] The main limitation of such studies is that they can underestimate ADE rate because they rely on International Classification of Diseases codes [START_REF] Edwards | Adverse drug reactions: definitions, diagnosis, and management[END_REF] and because ADEs are frequently underreported. [START_REF] Hazell | Under-reporting of adverse drug reactions: a systematic review[END_REF] Moreover, because of the variety of coding processes and of methods used to identify ADEs in administrative data, these analyses are much more difficult than the use of raw data. [START_REF] Hohl | ICD-10 codes used to identify adverse drug events in administrative data: a systematic review[END_REF] In our study, we included 5.9% of all patients who visited our ED. This rate is slightly higher than in comparable studies that included between 1.6% and 3.5% of patients presenting at the ED. [START_REF] Roulet | Implementing a clinical pharmacy survey of adverse drug events in a French emergency department[END_REF][START_REF] Roulet | Assessment of adverse drug event recognition by emergency physicians in a French teaching hospital[END_REF][START_REF] Asseray | Frequency and severity of adverse drug reactions due to self-medication: a cross-sectional multicentre survey in emergency departments[END_REF][START_REF] Roulet | Establishing a pharmacy presence in the emergency department: opportunities and challenges in the French setting[END_REF] - ---------------------------------------------------------------------------------------------------------------Data are presented as mean ± standard deviation or n (%). FRENCH triage scale level 1: immediately life-threatening; level 2: marked impairment of a vital organ, or imminently lifethreatening, or functionally disabling traumatic lesion; level 3: functional impairment, or organic lesions likely to deteriorate within 24 h, or complex medical situation justifying the use of several hospital resources; level 4: stable, noncomplex functional impairment or organic lesions, but justifying the urgent use of at least one hospital resource; level 5: no functional impairment or organic lesion justifying the use of hospital resources. -----------------------------------------------------------------------------------------------------------------In our analysis, we found that approximately 15% of ED visits were related to an ADE, in accordance with prospective studies reporting rates between 10% and 19%.4-6 The most common symptoms associated with ADEs were bleeding, endocrine, neurologic, and gastrointestinal problems, as previously reported. 48 In agreement with various studies, [START_REF] Patel | Drug-related visits to the emergency department: how big is the problem?[END_REF][START_REF] Roulet | Assessment of adverse drug event recognition by emergency physicians in a French teaching hospital[END_REF] 20.5% of post-ED hospitalizations and 52.0% of deaths at ED were due to an ADE. The post-ED hospitalization rate was slightly higher, and mortality was fivefold higher (1% versus 0.2%) in the ADE than non-ADE group, similarly to the 3.5-fold death increase reported by Classen et al. [START_REF] Classen | Adverse drug events in hospitalized patients. Excess length of stay, extra costs, and attributable mortality[END_REF] As previously described, the medications most involved in ADE (66% of cases) were nervous system, blood and blood forming organ, and cardiovascular system drugs .11 In addition, during the medication history interview for medication reconciliation and BPMH, we recorded all the drugs taken by the patient, which allowed us to calculate ADE rate per class (Anatomical Therapeutic Classification [ATC] 1st level) and subclass (ATC 2nd level) of medications, which is usually not done in studies on ADEs. This is particularly important for the clinical practice. For example, antineoplastic and immunomodulating agents ranked fifth in terms of number of ADEs but were first in terms of occurrence. To our knowledge, this is the first time that a prospective study presents ADE incidence in function of the drug class and subclass in a cohort of more than 8000 patients with 42,511 medications.

Another originality of our study was to analyze risk factors for each ADE categories (direct ADRs, participating ADRs, and noncompliance) and for severe ADE. We found that age was not independently associated with ADE risk (all categories), in agreement with most studies, [START_REF] Pedros | Prevalence, risk factors and main features of adverse drug reactions leading to hospital admission[END_REF][START_REF] Alexopoulou | Adverse drug reactions as a cause of hospital admissions: a 6-month experience in a single center in Greece[END_REF][START_REF] Leendertse | Frequency of and risk factors for preventable medication-related hospital admissions in the Netherlands[END_REF][START_REF] Andreazza | Causes of drug-related problems in the emergency room of a hospital in southern Brazil[END_REF] but not all. [START_REF] Alhawassi | A systematic review of the prevalence and risk factors for adverse drug reactions in the elderly in the acute care setting[END_REF][START_REF] Kongkaew | Risk factors for hospital admissions associated with adverse drug events[END_REF] Differences in ADE definition and in the patient populations may explain this heterogeneity among studies. On the other hand, age was an independent risk factor of participating ADR and severe ADEs. Medications for blood and blood-forming organs, antineoplastic and immunomodulating agents, and anti-infective drugs for systemic use were independent risk factors of all ADEs, as previously reported [START_REF] Alhawassi | A systematic review of the prevalence and risk factors for adverse drug reactions in the elderly in the acute care setting[END_REF][START_REF] Shehab | US emergency department visits for outpatient adverse drug events, 2013-2014[END_REF][START_REF] Oscanoa | Hospital admissions due to adverse drug reactions in the elderly. A meta-analysis[END_REF] and also of severe ADEs (except for anti-infective drugs). Moreover, ED visit to the emergency critical care and short stay hospitalization unit (i.e., the highest ED priority) were associated with ADEs and also severe ADEs. This information might contribute to improve the detection and management of patients with ADEs. In case of direct ADRs, a medication change or dosage adjustment may be proposed, whereas for noncompliance, a specific therapeutic education can be proposed. The most complex care management concerns patients with participating ADRs where the medication is not the only cause of the clinical event but also an aggravating factor. Accordingly, participating ADRs were associated with risk of severe ADE.

Our study has many strengths. To our knowledge, this is the first prospective study that analyzed the rate, severity, and independent risk factors in different categories of ADEs detected by clinical pharmacists in a cohort of more than 8000 adult patients in an ED. Our ED population included all types of adult patients visiting an ED and was not limited to specific classes of medications. The rigorous prospective data collection performed by the pharmacist team included demographic, clinical, biological, and therapeutic data as well as information on the (correct or incorrect) use of treatments by the patient, self-medication, and medication adherence. This allowed us to assess ADE association with many variables related to the patients, their ED visit, and their treatment, in a more comprehensive manner than previously done. 35 Finally, our study provides a robust estimate of ADE-related ED visits because f several methodological strengths. First, integrating the clinical pharmacist team in the ED for BPMH collection and medication reconciliation ensured a high level of ADE detection, particularly of participating ADRs. Second, an expert committee reviewed suspect cases, ensuring correct ADE diagnosis and classification.

- ---------------------------------------------------------------------------------------------------------------Abbreviations: FRENCH, 26 level 1: immediately life-threatening; level 2: marked impairment of a vital organ, or imminently life-threatening, or functionally disabling traumatic lesion; level 3: functional impairment, or organic lesions likely to deteriorate within 24 h, or complex medical situation justifying the use of several hospital resources; level 4: stable, noncomplex functional impairment, or organic lesions, but justifying the urgent use of at least one hospital resource; level 5: no functional impairment or organic lesion justifying the use of hospital resources; GFR, glomerular filtration rate. Abbreviation: GFR, glomerular filtration rate. -----------------------------------------------------------------------------------------------------------------Our study also has some limitations. Its monocentric design and our recruitment method may limit the generalization of our results, because of selection bias. First, pharmacists were present only during working days/hours and only 5.9% of patients who visited ED were included. However, patients visiting the ED during night or weekend and who were still present during working hours/days could be included (31.2% of our sample). Second, according to the French regulation, we included only patients who gave their consent for the study. However, only few patients refused (<1%), because the pharmacist's intervention is a routine practice in our ED. Because of the very small number of refusals, we did not record them, but the risk of recruitment bias seems negligible. Noninclusions due to psychological disturbance or voluntary poisoning not only were recorded but also represented a very small number of patients.

Another limitation comes from the decision to analyze only patients with outmissing data rather than using a multiple imputation method to replace missing data. This could result in a possible bias in the regression coefficients. However, because of the large number of patients and the small number of missing data for most variables, a multiple imputation approach was not included in our methodology. Lastly, our study highlighted the helpful role played by a pharmaceutical team integrated in an ED, as already described in endocrinology32 and surgery departments.52 Nevertheless, our observational design, without any control arm, does not allow to conclude about the specific role of pharmacists to improve the quality of care.

-----------------------------------------------------------------------------------------------------------------Abbreviations: FRench Emergency Nurses Classification in Hospital scale (FRENCH) ,26 level 1: immediately life-threatening; level 2: marked impairment f a vital organ, or imminently life-threatening, or functionally disabling traumatic lesion; level 3: functional impairment, or organic lesions likely to deteriorate within 24 h, or complex medical situation justifying the use of several hospital resources; level 4: stable, noncomplex functional impairment or organic lesions, but justifying the urgent use of at least one hospital resource; level 5: no functional impairment or organic lesion justifying the use of hospital resources; GFR, glomerular filtration rate. -----------------------------------------------------------------------------------------------------------------

CONCLUSIONS

In summary, 15.7% (n = 1299) of our large ED population (n = 8275) had ADEs detected by the pharmacist team and confirmed by the ED physician or expert committee. Most ADEs (71%) were related to a medication directly or indirectly, whereas 24% of ADEs were related to noncompliance with the prescription, and 5% had an undetermined cause. The most common ADE symptoms were bleeding, endocrine and neurologic problems, and were caused by anticoagulants, antibiotics, and antineoplastic/ immunomodulating agents. Finally, male sex, ED visit for neurologic problems, visit to the emergency critical care or to short stay hospitalization units, as well as blood, anti-infective, antineoplastic, and immunomodulating treatments were independent risk factors of ADE. Such risk factors may help primary care providers prioritize patients for medication reconciliation and detect rapidly ADE related ED visit, to reduce morbidity and mortality.

ACKNOWLEDGMENTS

The authors thank Professor Sylvie Hansel-Esteller and Professor Jean-Jaques Eledjam, the pharmacy residents and students of clinical pharmacy department, the emergency physicians and nurses, and the emergency department at Montpellier University Hospital for their ongoing support throughout the study.