Marthe Bonamy
email: marthe.bonamy@u-bordeaux.fr

Edouard Bonnet
email: edouard.bonnet@dauphine.fr

Nicolas Bousquet
email: nicolas.bousquet@grenoble-inp.fr

Pierre Charbit
email: charbit@irif.fr

Stéphan Thomassé
email: stephan.thomasse@ens-lyon.fr

Édouard Bonnet

EPTAS for Max Clique on Disks and Unit Balls

Keywords:

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

Introduction

In an intersection graph, the vertices are geometric objects with an edge between any pair of intersecting objects. Intersection graphs have been studied for many different families of objects due to their practical applications and their rich structural properties [START_REF] Brandstädt | Graph classes: a survey[END_REF][START_REF] Mckee | Topics in intersection graph theory[END_REF]. Among the most studied ones are disk graphs, which are intersection graphs of closed disks in the plane, and their special case, unit disk graphs, where all the radii are equal. Their applications range from sensor networks to map labeling [START_REF] Fishkin | Disk graphs: A short survey[END_REF], and many standard optimization problems have been studied on disk graphs, see for example [START_REF] Van Leeuwen | Optimization and Approximation on Systems of Geometric Objects[END_REF] and references therein. Most of the hard optimization and decision problems remain NP-hard on disk graphs and even unit disk graphs. For instance, disk graphs contain planar graphs [START_REF] Koebe | Kontaktprobleme der konformen Abbildung[END_REF] on which several XX:2 EPTAS for Max Clique on Disks and Unit Balls of those problems are untractable. Although shifting techniques and separator theorems may often lead to subexponential classic or parameterized algorithms [START_REF] Alber | Geometric separation and exact solutions for the parameterized independent set problem on disk graphs[END_REF][START_REF] Biró | Fine-grained complexity of coloring unit disks and balls[END_REF][START_REF] Marx | Optimal parameterized algorithms for planar facility location problems using voronoi diagrams[END_REF][START_REF] Smith | Geometric separator theorems & applications[END_REF]. Many approximation algorithms have been designed specifically on (unit) disk graphs, or more generally on geometric intersection graphs, see for instance [START_REF] Chan | Polynomial-time approximation schemes for packing and piercing fat objects[END_REF][START_REF] Erlebach | Polynomial-time approximation schemes for geometric intersection graphs[END_REF][START_REF] Gibson | Algorithms for dominating set in disk graphs: Breaking the logn barrier -(extended abstract)[END_REF][START_REF] Nieberg | A PTAS for the minimum dominating set problem in unit disk graphs[END_REF][START_REF] Nieberg | A robust PTAS for maximum weight independent sets in unit disk graphs[END_REF][START_REF] Van Leeuwen | Better approximation schemes for disk graphs[END_REF] to cite only a few. Besides ad hoc techniques, local search and VC-dimension play an important role in the approximability of problems on (unit) disk graphs. For the main packing and covering problems (Maximum Independent Set, Min Vertex Cover, Minimum Dominating Set, Minimum Hitting Set, and their weighted variants) at least a PTAS is known.

However, all the techniques that we mentioned are only amenable to packing and covering problems. The Maximum Clique problem is arguably the most prominent problem which does not fall into those categories. For example, anything along the lines of exploiting a small separator cannot work for Maximum Clique, where the densest instances are the hardest. Therefore, it seems that new ideas are necessary to get improved approximate or exact algorithms for this problem. This is why, in this paper, we focus on solving Maximum Clique on (unit) disk graphs in dimension 2 or higher.

Previous results.

In 1990, Clark et al. [START_REF] Clark | Unit disk graphs[END_REF] gave an elegant polynomial-time algorithm for Maximum Clique on unit disk graphs when the input is a geometric representation of the graph. It goes as follows: guess in quadratic time the two more distant centers of disks in a maximum clique, remove all the centers that would contradict this maximality, observe that the resulting graph is co-bipartite, implying that an optimum solution can be found in polynomial time. However, recognizing unit disk graphs is NP-hard [START_REF] Breu | Unit disk graph recognition is NP-hard[END_REF], and even ∃R-complete [START_REF] Kang | Sphere and Dot Product Representations of Graphs[END_REF]. In particular, if the input is the mere unit disk graph, one cannot expect to efficiently compute a geometric representation in order to run the previous algorithm. Raghavan and Spinrad showed how to overcome this issue and suggested a polynomial-time algorithm which does not require the geometric representation [START_REF] Raghavan | Robust algorithms for restricted domains[END_REF]. Their algorithm is a subtle blind reinterpretation of the algorithm by Clark et al. It solves Maximum Clique on a superclass of the unit disk graphs or correctly claims that the input is not a unit disk graph. Hence, it cannot be used to efficiently recognize unit disk graphs.

The complexity of Maximum Clique on general disk graphs is a notorious open question in computational geometry. On the one hand, no polynomial-time algorithm is known, even when the geometric representation is given. On the other hand, the NP-hardness of the problem has not been established, even when only the graph is given as input.

The piercing number of a collection of geometric objects is the minimum number of points that hit all the objects. It is known since the fifties (although the first published records of that result came later in the eighties) that the piercing number of pairwise intersecting disks is 4 [START_REF] Danzer | Zur lösung des gallaischen problems über kreisscheiben in der euklidischen ebene[END_REF][START_REF] Stachó | A solution of gallai's problem on pinning down circles[END_REF]. An account of this story can be found in a recent note by Har-Peled et al. [START_REF] Har-Peled | Stabbing pairwise intersecting disks by five points[END_REF]. Ambühl and Wagner observed that this yields a 2-approximation for Maximum Clique [START_REF] Ambühl | The Clique Problem in Intersection Graphs of Ellipses and Triangles[END_REF]. Indeed, after guessing in polynomial time four points hitting a maximum clique and removing every disk not hit by those points, the instance is partitioned into four cliques; or equivalently, two co-bipartite graphs. One can then solve optimally both instance formed by one co-bipartite graph and return the larger solution. This cannot give a solution more than twice smaller than the optimum. Since then, the problem has proved to be elusive with no new positive or negative results. The question on the complexity and further approximability of Maximum Clique on general disk graphs is considered as folklore [START_REF] Bang-Jensen | On six problems posed by Jarik Nešetřil[END_REF], but was also explicitly mentioned as an open problem by Fishkin [START_REF] Fishkin | Disk graphs: A short survey[END_REF], Ambühl and Wagner [START_REF] Ambühl | The Clique Problem in Intersection Graphs of Ellipses and Triangles[END_REF]. Cabello even asked if there is a 1.99-approximation for disk graphs with two sizes of radii [START_REF] Cabello | Maximum clique for disks of two sizes. Open problems from Geometric Intersection Graphs: Problems and Directions CG Week Workshop[END_REF][START_REF] Cabello | Open problems presented at the Algorithmic Graph Theory on the Adriatic Coast workshop[END_REF]. Recently, Bonnet et al. [START_REF] Bonnet | QPTAS and subexponential algorithm for maximum clique on disk[END_REF] showed that the disjoint union of two odd cycles is not the complement of a disk graph. From this result, they obtained a subexponential algorithm running in time 2 Õ(n 2/3 ) for Maximum Clique on disk graphs, based on a win-win approach. They also got a QPTAS by calling a PTAS for Maximum Independent Set on graphs with sublinear odd cycle packing number due to Bock et al. [START_REF] Bock | Solving the Stable Set Problem in Terms of the Odd Cycle Packing Number[END_REF], or branching on a low-degree vertex.

Our results.

Our main contributions are twofold. The first is an EPTAS (Efficient Polynomial-Time Approximation Scheme, that is, a PTAS in time f (ε)n O (1) ) for Maximum Independent Set on graphs of X (d, β, 1) with constant VC-dimension d, independence number at least βn, and no disjoint union of two odd cycles as an induced subgraph. (1) for Maximum Independent Set on graphs of X (d, β, 1) with n vertices.

Theorem 1. For any constants

d ∈ N, 0 < β 1, for every 0 < ε < 1, there is a randomized (1 -ε)-approximation algorithm running in time 2 Õ(1/ε 3 ) n O
Using the forbidden induced subgraph result of Bonnet et al. [START_REF] Bonnet | QPTAS and subexponential algorithm for maximum clique on disk[END_REF], it is then easy to reduce Maximum Clique on disk graphs to Maximum Independent Set on X (3, β, 1) for some constant β. We therefore obtain an EPTAS for Maximum Clique on disk graphs, settling almost1 completely the approximability of this problem.

Theorem 2. There is a randomized EPTAS for Maximum Clique on disk graphs, even without geometric representation. Its running time is 2 Õ(1/ε 3 ) n O (1) for a (1 -ε)approximation on a graph with n vertices.

The second contribution is to show the same forbidden induced subgraph for unit ball graphs as the one obtained for disk graphs. The proofs are radically different and the classes are incomparable. So the fact that the same obstruction applies for disk graphs and unit ball graphs might simply be a coincidence.

Theorem 3. A complement of a unit ball graph cannot have a disjoint union of two odd cycles as an induced subgraph. In other words, if G is a unit ball graph, then iocp(G) 1.

In the previous statement iocp denotes the induced odd cycle packing number of a graph, i.e., the maximum number of odd cycles as a disjoint union in an induced subgraph. Again, Theorem 1 and Theorem 3 naturally lead to: Theorem 4. There is a randomized EPTAS in time 2 Õ(1/ε 3 ) n O (1) for Maximum Clique on unit ball graphs, even without the geometric representation.

Before that result, the best approximation factor was 2.553, due to Afshani and Chan [START_REF] Afshani | Approximation algorithms for maximum cliques in 3d unit-disk graphs[END_REF]. In particular, even getting a 2-approximation algorithm (as for disk graphs) was open.

Finally we show that such an approximation scheme, even in subexponential time, is unlikely for ball graphs, and unit 4-dimensional disk graphs. Our lowerbounds also imply NP-hardness. To the best of our knowledge, the NP-hardness of Maximum Clique on unit d-dimensional disk graphs was only known when d is superconstant (d = Ω(log n)) [START_REF] Afshani | Approximation and inapproximability results for maximum clique of disc graphs in high dimensions[END_REF].

In the following paragraphs, we sketch the principal lines of our two main contributions.

EPTAS for Maximum Independent Set on X (d, β, 1)

The first main result of this paper asserts that if a graph G satisfies that every two odd cycles are joined by an edge, the Vapnik-Chervonenkis dimension of the hypergraph of the neighborhoods of G is bounded, and α(G) is at least a constant fraction of |V (G)|, then α(G) can be computed in polytime at any given precision. More precisely, we present in that case a randomized EPTAS running in time 2 Õ(1/ε 3 ) n O (1) and a deterministic PTAS.

Our algorithm works as follows. We start by sampling hopefully in a fixed optimum solution I. We include the selected vertices in our solution and remove their neighborhood from the graph. Due to the classic result of Haussler and Welzl [START_REF] Haussler | Epsilon-nets and simplex range queries[END_REF] on ε-nets of size O(d/ε log 1/ε) (where d is the VC-dimension), this sampling lowers the degree in I of the remaining vertices. We compute a shortest odd cycle. If this cycle is short, we can remove its neighborhood from the graph and solve optimally the problem in the resulting graph, which is bipartite by assumption. If this cycle is long, we can efficiently find a small oddcycle transversal. This is shown by a careful analysis on the successive neighborhoods of the cycle, and the recurrent fact that this cycle is the shortest among the ones of odd length.

The complement of the union of two odd cycles is not a unit ball graph

Given a needle in R 3 whose middlepoint is attached to the origin, one can apply a continuous motion in order to turn it around (a motion à la Kakeya, henceforth Kakeya motion). If we now consider two needles, each with a Kakeya motion, then the two needles will go through the same position. This simply follows from the fact that two antipodal curves on the 2sphere intersect. The second main result of this paper is a translation of this Jordan-type theorem in terms of intersection graphs: The complement of unit balls does not contain the disjoint union of two odd cycles. The proof can really be seen as two Kakeya motions, each one along the two odd cyles, leading to a contradiction when the needles achieve parallel directions.

Together with the first result, it implies a randomized EPTAS for Maximum Clique on disk graphs, and for the following problem: Given a set S of points in R 3 , find a largest subset of S of diameter at most 1.

Organization

The rest of the paper is organized as follows. In Section 2, we recall some relevant notations for graphs and elementary geometry, the definitions of VC-dimension, disk graphs, and approximation schemes. We finish this section by introducing a class of graphs parameterized by three constants: the VC dimension, the ratio independence number divided by number of vertices, and the maximum number of odd cycles that can be found as a disjoint union in an induced subgraph. In Section 3, we design a randomized EPTAS for Maximum Independent Set on this class. In Section 4, we show that complements of unit ball graphs do not have a disjoint union of two odd cycles as an induced subgraph. This yields a randomized EPTAS for Maximum Clique on unit ball graphs (as well as on disk graphs). This is tight in two directions: having different values of radii, and the dimension of the ambient space. Indeed, we complement this positive result by showing that Maximum Clique is unlikely to even have a QPTAS on ball graphs where all the radii are arbitrarily close to 1, and on 4-dimensional unit ball graphs.

Preliminaries

Graph notations

Let G be a simple graph. We denote by G its complement, i.e., the graph obtained by making every non-edge an edge and vice versa. V (G) and E(G) represent its set of vertices and its set of edges, respectively. We denote by α(G) the independence number of G, i.e., the size of a maximum independent set (or stable set), and by ω(G) the clique number of G, i.e., the size of a maximum clique. For S ⊆ V (G), its open neighborhood, denoted by N G (S), is the set of vertices that are not in S and have a neighbor in S, and its closed neighborhood is defined by

N G [S] = S ∪ N G (S)
. We omit the subscript G if the graph is obvious from the context and we write

N G (x) instead of N G ({x}).
The odd cycle packing number of G, denoted by ocp(G), is defined as the maximum number of vetex-disjoint odd cycles and the induced odd cycle packing number of G, denoted iocp(G), is the maximum number of vertex-disjoint odd cycles with no edge between any two of them.

VC-dimension

VC-dimension has been introduced by Vapnik and Chervonenkis in the seminal paper [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]. Let H = (V, E) be a hypergraph. A set X of vertices of H is shattered if for every subset Y of X there exists a hyperedge e ∈ E such that e ∩ X = Y . An intersection between X and a hyperedge e of E is called a trace (on X). Equivalently, a set X is shattered if all its 2 |X| traces exist. The VC-dimension of a hypergraph is the maximum size of a shattered set. As an abuse of language, we call VC-dimension of a graph G, denoted by VCdim(G), the VC-dimension of the hypergraph (

V (G), {N G (v) | v ∈ V (G)}).

Geometric notations

For a positive integer d, we denote by R d the d-dimensional euclidean space. If x and y are two points of R d , xy is the straight-line segment whose endpoint are x and y. We denote by d(x, y) the euclidean distance between x and y. A d-dimensional closed disk is defined from a center x ∈ R d and a radius r ∈ R + , as the set of points {y ∈ R d | d(x, y) r}, i.e., at distance at most r from x. The diameter of a subset S ⊆ R d is the quantity sup x,y∈S

d(x, y).

The piercing number (also called hitting set or transversal) of a collection O of geometric objects in R d is the minimum number of points of R d that pierce (or hit) all the objects of O, i.e., each object contains at least one of these points.

Disk graphs and their forbidden induced subgraphs

A d-dimensional disk graph is the intersection graph of d-dimensional closed disks of R d . We shorten 2-dimensional disk graph in disk graph, and 3-dimensional disk graph in ball graph. A d-dimensional unit disk graph is the intersection graph of unit d-dimensional closed disks of R d ,
that is, disks with radius 1. Unit d-dimensional disk graphs can be thought of only with points: vertices are points (at the center of the disks) and two points are adjacent if they are at distance at most 2. In particular, solving Maximum Clique on those graphs is equivalent to finding a maximum subcollection of points whose diameter is at most a fixed value.

Bonnet et al. established the following obstruction for disk graphs.

Theorem 5 ([10]). The complement of a disk graph cannot have the disjoint union of two odd cycles as an induced subgraph.

This can be equivalently rephrased as: if G is a disk graph, then iocp(G) 1.

Approximation schemes

A PTAS (Polynomial-Time Approximation Scheme) for a minimization (resp. maximization) problem is an approximation algorithm which takes an additional parameter ε > 0 and outputs in time n f (ε) a solution of value at most (1 + ε)OPT (resp. at least (1 -ε)OPT) where OPT is the optimum value. Observe that from now on, we consider that approximation ratios of maximization problems are smaller than 1, unlike the convention we used in the introduction. An EPTAS (Efficient PTAS) is the same with running time f (ε)n O (1) , an FPTAS (Fully PTAS) is in time 1) , a QPTAS (Quasi PTAS) is in time n polylog n for every ε. Finally, and this is quite informal and not standard, we call SUBEXPAS (subexponential AS) an approximation scheme with running time 2 n 0.99 for every ε. All those approximation schemes can come deterministic or randomized.

1 ε O(1) n O(

The class X (d, β, i)

In the next section, we present a randomized EPTAS and a deterministic PTAS for approximating the independence number α on graphs with constant VC-dimension, linear independence number, and induced odd cycle packing number equals to 1.

Actually, we extend these algorithms to the case iocp(G) = i, for any constant i. Let X (d, β, i) be the class of simple graphs G satisfying:

VCdim(G) d, α(G) β|V (G)|, and iocp(G) i.
For any positive constants d, β < 1, i, we get a deterministic PTAS and a randomized EPTAS for Maximum Independent Set on X (d, β, i). It will turn out that the complement of the interesting instances are in X (3, 1 6 , 1) (or X (3, 1 4 , 1)) for disk graphs, and in X (4, 1 12 , 1) for unit ball graphs.

EPTAS for Maximum Independent Set on X (d, β, i)

We start by showing that X (d, β, 1) has a randomized EPTAS. (1) for Maximum Independent Set on graphs of X (d, β, 1) with n vertices.

Theorem 1. For any constants d ∈ N, 0 < β 1, for every 0 < ε < 1, there is a randomized (1 -ε)-approximation algorithm running in time 2 Õ(1/ε 3 ) n O
Proof. Let H be a graph in X (d, β, 1) with n vertices and I be a maximum independent set of H. In particular, |I| βn. Since finding a maximum independent set in a bipartite graph can be done in polynomial time, we get the desired (1 -ε)-approximation if we can find a vertex-set T such that:

T is an odd-cycle transversal, i.e., its removal yields a bipartite graph, and |T ∩ I| ε|I|.

At high level, our algorithm will thus select and remove some odd-cycle transversals T , and then apply the bipartite case algorithm. We will do this at least once for a set T that satisfies the second item, with some strong guarantee. Of course the key ingredient in finding a suitable odd-cycle transversal is the fact that iocp(H) 1. For instance, this implies that for any odd cycle C, the set N [C] is an odd-cycle transversal.

Let

c := 8( 1 (βε) 2 + 1 βε + 1) = O(1/ε 2 ), δ := ε c = O(ε 3 )
, and s := 10d δ log 1 δ . We call short odd cycle an odd cycle of length at most c, and long odd cycle an induced odd cycle of length more than c. First we can assume that βn is larger than 2s, otherwise we can find an optimum solution by brute-force in time 2 n = 2 Õ(1/ε 3 ) . Hence, |I| > 2s.

Claim 1. There exists a subset S ⊆ I of size s = 10d δ log 1 δ such that N (S) contains all vertices that have more than δ|I| neighbors in I.

Proof. Let A denote the set of vertices v such that |N (v) ∩ I| δ|I|. We define the hypergraph K := (I, {N (v) ∩ I, v ∈ A}).
By assumption on H, the hypergraph K has VCdimension d. By definition of K, all its edges have size at least δ|V (K)|. A celebrated result in VC-dimension theory by Haussler and Welzl [START_REF] Haussler | Epsilon-nets and simplex range queries[END_REF], later improved by Blumer et al. [START_REF] Blumer | Learnability and the vapnik-chervonenkis dimension[END_REF], ensures that every such hypergraph K admits a hitting set (a set of vertices that intersects every edge) of size at most 10d δ log 1 δ .

Algorithmically, we have two ways of selecting the set S, leading to a deterministic PTAS or a randomized EPTAS. Either we run the rest of the algorithm for every subset of V (H) of size 10d δ log 1 δ inducing an independent set (which constitutes n f (ε) possible sets), or we use another result proven in [START_REF] Haussler | Epsilon-nets and simplex range queries[END_REF]: not only the hitting set exists but a uniform sample of V (K) of size 10d δ log 1 δ is a hitting set with high probability. So we do the following t := log(10 -10 ) log(1-(β/2) s ) = 2 Õ(1/ε 3 ) many times: we select uniformly at random a set S of size s = 10d δ log 1 δ , and continue the rest of the algorithm if S is an independent set. Since |I| > 2s, it holds that Pr(S ⊆ I) > (β/2) s . As we try out t samples, at least one satisfies S ⊆ I with probability at least 1 -(1 -(β/2) s ) t 1 -10 -10 .

We now assume that the sample S satisfies the properties of Claim 1. We start by putting in T all the vertices of N (S) (note that no such vertex is in I). We define the graph H := H -N (S). We got rid of the vertices with at least δ|I| neighbors in I: in H , there are no such vertices anymore. We want to find an odd-cycle transversal in H that has few vertices in I.

We now run a polynomial-time algorithm (see for instance [START_REF] Alon | Finding and counting given length cycles[END_REF]) that determines whether the graph is bipartite and, if not, outputs a shortest odd cycle C og in H .

If H is bipartite, then T := N H (S) is an odd-cycle transversal of H with |T ∩ I| = 0. If g = |C og | c, that is, if C og is a short odd cycle, then |N H (C og ) ∩ I| cδ|I| = ε|I|, and therefore T := N H (S)∪N H [C og ] is an odd-cycle transversal of H with |T ∩I| ε|I|.
We can now safely assume that g > c, i.e., C og is a long odd cycle. We decompose H into the successive neighborhoods of C og , which we call layers. We define the first layer as L 1 := N H (C og ). We define by induction the other layers as the non-empty sets L i := {v | ∃u ∈ L i-1 with uv ∈ E(H ) and v / ∈ L j for j < i}. Let us denote by λ the index of the last non-empty layer. Before entering into the formal details of the second part of the proof let us briefly explain its structure: First, we observe that if there are many layers, there is one with index at most In other words, we can find ε|I| vertices whose deletion yields a bipartite graph (see Figure 1), which together with N (S) form the desired odd-cycle transversal.

Figure 1 The layers (columns) and the strata (rows of a column). If the number of successive neighborhoods is large, a small cutset (in blue) is found among the first 2 βε layers. To the right of this cutset, we know that the graph is bipartite. This brings us back to the case with fewer than 2 βε layers, where we can find a small odd cycle transversal (in red).

If λ > 2

βε , then there is some index i 2 βε such that L i is of size at most βε 2 n ε 2 |I|. We remove that layer L i from the graph. Since iocp(H ) = 1, the set i<j λ L j induces a bipartite graph. Indeed, it is disjoint from the closed neighborhood of the odd cycle C og . We can easily find a maximum independent set on this part of the graph, and focus on the other part, which is C og ∪ 1 j<i L j . We set

H := H [C og ∪ 1 j<i L j ].
The graph H has less than 2 βε layers emanating from C og . We will find an odd-cycle transversal of size at most ε 2 |I|. We first need some new definitions. For 1 j g, let S j be the set of vertices w ∈ V (H ) such that there is a shortest path from w to C og which ends in v j , while no shortest path from w to C og ends in v i with i < j (note that v j ∈ S j ). We point out that the sets (S 1 , . . . , S g ) induce a partition of each layer L k . This simply follows from the fact that for every vertex w ∈ L k , there is a minimum index j(w) such that there is a shortest path from v to C og ending in v j(w) . For each pair (k, ), we define a stratum as

L k := S ∩ L k . Note that if L k = ∅, then for any k > k, L k = ∅.
Let z := 4 βε +2 and for any non-negative integer γ at most g z -1, S γ := γz+1 j (γ+1)z S j .

Claim 2. For any non-negative integer γ 2 βε , the graph B := H -S γ is bipartite.

Proof. Observe that g z -1

2 βε , so each S γ of the claim is well-defined. It holds that C og ∩ S γ = γz+1 j (γ+1)z {v j }. We exhibit a proper 2-coloring of B by coloring its vertices as follows. We start by coloring each vertex of the path C og \ S γ in an alternated manner, i.e., one endpoint of the path gets color 0, its neighbor gets color 1, the next vertex gets color 0, and so on.

For each pair (k, ) such that 1 k < i, 1 g, and / ∈ [γz + 1, (γ + 1)z], we color all the vertices in the stratum L k = S ∩ L k with the opposite color of the one used for the stratum L k-1 = S ∩ L k-1 (with the convention that L 0 := C og ). This process colors unambiguously all the vertices of B.

Let us prove that the resulting coloring is proper. First note that the vertices of a same stratum form an independent set. Indeed, assume by contradiction that L k contains an edge uw. There is a shortest path P 1 from v to u and a path P 2 from w to v . Since u and w are in the same layer L k , P 1 and P 2 have the same length; more precisely,

|P 1 | = |P 2 | = k < i 2 βε .
Thus, P 1 , uw, P 2 defines a closed walk with 2k +1 edges. An odd closed walk of length 2k +1 implies the existence of an odd induced cycle of length at most 2k+1. As 2k+1 < 4 βε +1 < g, we reach a contradiction on the minimality of C og .

There is no edge between a stratum L k and a stratum L k with |k -k | 2, by definition of the layers. Moreover, for 1 < g, there is no edge uw with u ∈ L k and w ∈ L k with min( -, +g -) 4 βε +1 since otherwise it would be possible to construct a shorter odd cycle than C og . Indeed if P 1 is a shortest path between v and u and P 2 is a shortest path between w and v . Then, P 1 , uw, P 2 is an odd walk of length k + k + 1. However, a shortest path between v and v within C og has length min( -, + g -)

4 βε + 1 > k + k + 1.
Hence, the walk P 1 , uw, P 2 can be extended into an odd closed walk of length stricly smaller than g, by taking the path from v to v in C og with the same parity as k+k ; a contradiction. Therefore, if there is a monochromatic edge uw in B, it must be between L k and L k with -k | ∈ {0, 1}, min( -, + g -) < 4 βε + 1, and { , } ∩ [γz + 1, (γ + 1)z] = ∅. We fix k, k , , satisfying those conditions. We call small interval of and , denoted by si( , ), the integer interval [ , ] if min( -, + g -) = -and [ , g] ∪ [1, ] if min( -, + g -) = + g -. What we showed in the previous paragraph implies that if { , } ∩ [γz + 1, (γ + 1)z] = ∅, then si( , ) ∩ [γz + 1, (γ + 1)z] = ∅. Indeed, the small interval of and is a circular interval over [1, g] of length less than 4 βε + 1 < z. In particular, the vertices of C og indexed by the small interval of and are all in B.

Assume first that k = k . There is a path P 1 from v to u, and a path P 2 from w to v , both of length k. Since by assumption the color for L k is the same as the color for L k , the vertices v and v have the same color (by construction of the 2-coloring). Thus we have, in C og -S γ , a path P indexed by si( , ) from v to v of even length less than 4 βε + 1. We emphasize that it is crucial that si( , ) ∩ [γz + 1, (γ + 1)z] = ∅ (meaning that all the vertices of C og indexed by si( , ) are still in B), to deduce that P is a path of even length from the mere fact that v and v have the same color. Finally, the concatenation P 1 , uw, P 2 , P yields an odd cycle of odd length less than 2k + 1 + 4 βε + 1 8 βε + 2 < g. Now let us assume that |k -k | = 1; say, without loss of generality, k = k + 1. In that case, by construction of the 2-coloring, the edge can only be monochromatic if v and v receive distinct colors. Furthermore, there is a path P 1 from v to u, and a path P 2 from w to v with length of distinct parities (k and k + 1, respectively). Moreover, since v and v get distinct colors, there is in C og -S γ , a path P indexed by si( , ) from v to v of odd length at most 4 βε + 1. Again, we crucially use that all the vertices of C og indexed by si( , ) are in B, to deduce that P is of odd length from the fact that v and v get distinct colors. Finally, the concatenation P 1 , uw, P 2 , P is an odd cycle of length less than k + 1 + k + 1 + 4 βε + 1

XX:10 EPTAS for Max Clique on Disks and Unit Balls

Algorithm 1 EPTAS for Maximum Independent Set on X (d, β, 1)

Precondition: H satisfies d := VCdim(G) = O(1), α(G) β|V (G)|,
H ← H -N [S]
remove S and its neighborhood C og ← shortest odd cycle in H in polynomial time [START_REF] Alon | Finding and counting given length cycles[END_REF] 13:

g ← |C og | C og = v 1 v 2 . . . v g 14:
if g c then short odd cycle return S at the iteration maximizing its cardinality 28: end function Postcondition: output S is a stable set of size at least (1 -ε)α(G) with high probability Theorem 2. There is a randomized EPTAS for Maximum Clique on disk graphs, even without geometric representation. Its running time is 2 Õ(1/ε 3 ) n O (1) for a (1 -ε)approximation on a graph with n vertices.

S γ ← smallest set among { k∈[γz+1,(γ+1)z] S k } γ∈[0, 2 βε ] |S γ | ε 2 α(G)
Proof. With a geometric representation, we could invoke the following argument to get a linear maximum stable set. Recall that the piercing number of a family of geometric objects is the minimum number of points such that each object contains at least one of those points. The piercing number of a collection of pairwise intersecting disks in the plane is 4 [START_REF] Danzer | Zur lösung des gallaischen problems über kreisscheiben in der euklidischen ebene[END_REF][START_REF] Stachó | A solution of gallai's problem on pinning down circles[END_REF]. The number of faces in an arrangement of n circles (disk boundaries) is O(n 2 ), and all the points within one face hits the same disks. In time O(n 8 ), one can therefore exhaustively guess four points piercing a maximum clique C. We can remove all the disks which are not hit by any of those four points, since they are not part of C. This new instance G can have its vertices partitioned into four cliques, hence α(G)

|V (G)|/4.
Without a geometric representation, we suggest the following. Disk graphs are 6ωdegenerate (and closed by induced subgraphs), i.e., there is a vertex of degree at most 6ω, where ω is the clique number of the graph. Furthermore, the neighborhood of this vertex is easily partitionable into 6 cliques. We can find such a vertex in polynomial time. We branch on two outcomes. Either this vertex is in a maximum clique: we run the approximation of Theorem 1 on its closed neighborhood G which satifies α(G)

|V (G)|/6. Or this vertex is not in any maximum clique: we delete it from the graph. Our branching tree has size 2n + 1, so it only costs an extra linear multiplicative factor.

It is folklore that disk graphs have VC-dimension at most 3 (see for instance [START_REF] Bousquet | Identifying codes in hereditary classes of graphs and vc-dimension[END_REF]) and, since the VC-dimension of a graph is equal to the one of its complement, the VC-dimension of G is also at most 3. Finally, by Theorem 5 [START_REF] Bonnet | QPTAS and subexponential algorithm for maximum clique on disk[END_REF], iocp(G) 1. We only call the approximation algorithm (a polynomial number of times) with disk graphs G such that G ∈ X (3, 1 6 , 1) (argument without the geometric representation) or G ∈ X (3, 1 4 , 1) (argument with the geometric representation). Hence, we conclude by Theorem 1.

It is known that the VC-dimension of unit balls and the piercing number of pairwise intersecting unit balls are both constant. In Section 4, we will show that the induced odd cycle packing number of unit ball graphs is at most 1. This is the missing element for the EPTAS to also work for Maximum Clique on unit balls.

We conclude this section by extending the EPTAS to work for constant (not necessarily 1) induced odd cycle packing number. Theorem 6. For any constants d, i ∈ N, 0 < β 1, for every ε > 0, there is a randomized (1-ε)-approximation algorithm running in time 2 Õ(1/ε 3 ) n O (1) for Maximum Independent Set on graphs of X (d, β, i) with n vertices.

Proof. Let I be a maximum independent set. We show by induction on i that we can find in time 2 Õ(1/ε 3 ) n O (1) a stable set of size (1 -iε )|I|. The base case is Theorem 1. We assume that there is such an algorithm when the induced odd cycle packing number is i -1. We follow Algorithm 1 with a graph H such that iocp(H) = i. On line 15 and 23, the graph is not necessarily bipartite anymore (on line 24, the resulting graph is still bipartite in this case). Although, the induced odd cycle packing number is decreased to i -1. So, by the induction hypothesis we get a stable set within a factor (1 -(i -1)ε ) of the optimum. To get there, we removed a subset of vertices of size at most ε |I|. Therefore, the solution S that we obtain satisfies |S| (1 -iε )|I|.

We obtain the theorem by setting ε := iε since i is absorbed in the Õ in the running time.

Balls and higher dimensions

We start by showing the main result of this section: for every unit ball graph G, iocp(G) 1. A closed polygonal chain C in R d is defined by a set of points (or vertices) x 1 , x 2 , . . . , x p ∈ R d as the straight-edge segments x 1 x 2 , x 2 x 3 , . . . , x p-1 x p , x p x 1 . We call direction of a non-zero vector its equivalence class by the relation u ∼ v ⇔ ∃λ ∈ R + , u = λ v. We denote the direction of u by dir( u). We define the set of directions Needle(C) :=

1 i p [x i-1 ← x i → x i+1 ] ∪ [x i-1 → x i ← x i+1 ],
where the indices are taken modulo p,

[x i-1 ← x i → x i+1 ] := {dir( -→ x i x) | x ∈ x i-1 x i+1 }, and [x i-1 → x i ← x i+1 ] := {dir( -→ xx i ) | x ∈ x i-1 x i+1 }.
Lemma 7. Let C 1 and C 2 be two closed polygonal chains of R 3 on an odd number of vertices each. Then, Needle(C 1 ) ∩ Needle(C 2 ) is non-empty.

Proof. We want to establish the existence of a direction which is common to Needle(C 1 ) and Needle(C 2 ). For that, we yield a continuous map from R + to Needle(C 1 ) that we naturally interpret as a curve on the 2-sphere. Indeed the set of directions in R 3 is isomorphic to the set of points on the 2-sphere. As we do not need a specific parameterization of the curve, we just describe how we continuously move a vector -→ ab whose direction runs through the entire set Needle(C 1 ). Let x 1 , x 2 , . . . , x p be the vertices of C 1 .

We start with a in x 1 and b in x 2 . We continuously move a from x 1 to x 3 (on the straight-edge segment x 1 x 3 ) while b stays fixed at x 2 . For the next step, a is fixed at x 3 and b continuously moves from x 2 to x 4 . And in general, we move the point with index i -1 from x i-1 to x i+1 while the other point stays fixed at x i (where the indices are modulo p). Since p is odd, we reach the situation where b is in x 1 and a is in x 2 . We do the same one more time, so that a is back to x 1 and b is back to x 2 , and we stop. One may observe that this process spans Needle(C 1 ).

This defines a closed curve C 1 on the 2-sphere since we are finally back to dir( --→ x 1 x 2 ) from where we started. Furthermore, C 1 is antipodal, i.e., closed by taking antipodal points. Indeed, for each direction attained in a [x i-1 ← x i → x i+1 ], we attain the opposite direction in [x i-1 → x i ← x i+1 ]. Similarly Needle(C 2 ) draws a closed antipodal curve on the 2-sphere C 2 . The curves C 1 and C 2 intersect since they are closed and antipodal. An intersection point corresponds to a direction shared by Needle(C 1 ) and Needle(C 2 ).

We will apply this lemma on the closed polygonal chains C 1 and C 2 formed by the centers of unit balls realizing two odd cycle complements. The contradiction will come from the fact that not all the pairs of centers x ∈ C 1 and y ∈ C 2 can be at distance at most 2. Theorem 3. A complement of a unit ball graph cannot have a disjoint union of two odd cycles as an induced subgraph. In other words, if G is a unit ball graph, then iocp(G) 1.

Proof. Let x 1 , x 2 , . . . , x p ∈ R 3 (y 1 , y 2 , . . . , y q ∈ R 3 ) be the centers of unit balls representing the complement of an odd cycle of length p (resp. q), such that x i and x i+1 (resp. y i and y i+1 ) encode the non-adjacent pairs. Let C 1 (resp. C 2 ) be the closed polygonal chain obtained from the centers x 1 , x 2 , . . . , x p (resp. y 1 , y 2 , . . . , y q ). By Lemma 7, there are two collinear vectors -→

x i x and -→ y j y with x on the straight-line segment x i-1 x i+1 and y on the straight-line segment y j-1 y j+1 . Let suppose that -→ x i x and -→ y j y have the same direction (left of Figure 2). In the plane 2 containing x i , x, y j , and y, those four points are in convex position and the convex hull is cyclically ordered x i , x, y, y j . We obtain a contradiction by showing that the sum of the diagonals d(x i , y) + d(y j , x) is strictly smaller than the sum of two opposite sides d(x i , x) + d(y j , y).

Considering edges and non-edges, we have d(x i , y j-1 ) 2 < d(y j , y j-1 ) and d(x i , y j+1 ) 2 < d(y j , y j+1 ). The points strictly closer to x i than to y j is an open half-space. In particular, they form a convex set and all the points in the segment y j-1 y j+1 are therefore closer to x i than to y j . Hence, d(x i , y) < d(y j , y). Symmetrically, d(y j , x) < d(x i , x). So d(x i , y) + d(y j , x) < d(y j , y) + d(x i , x), a contradiction.

Let now assume that -→ x i x and -→ y j y have opposite direction (right of Figure 2). In that case, the four coplanar points x i , x, y j , y are in convex position in their plane and the convex hull is cyclically ordered x i , x, y j , y. We will attain the similar contradiction that d(x, y) + d(x i , y j ) < d(x i , x) + d(y j , y). As previously, d(y j-1 , x i-1 ) 2 < d(x i , x i-1 ) and d(y j-1 , x i+1 ) 2 < d(x i , x i+1 ). Hence, by convexity, we have d(y j-1 , x) < d(x i , x). Similarly, d(y j+1 , x) < d(x i , x). We obtained that point x is closer to y j-1 and y j+1 than to x i . Therefore, applying again the convexity argument, we get that d(x, y) < d(x, x i ). Besides, d(x i , y j ) 2 < d(y, y j ). So we arrive at the contradiction d(x, y) + d(x i , y j ) < d(x, x i ) + d(y, y j ).

It is folklore that unit ball graphs have VC-dimension 4. At the price of a multiplicative factor n in the running time, one can guess a vertex v in a maximum clique of a unit ball graph G, and look for a clique in its neighborhood H := G[N (v)]. It can be easily shown that the neighborhood of this vertex (in fact, of any vertex) can be partitioned into, say 50 cliques. But actually 12 cliques are enough following the proof of the kissing number for spheres. Thus α(H)

|V (H)|/12. Therefore, from Theorem 1 and Theorem 3, we immediately obtain the following. Theorem 4. There is a randomized EPTAS in time 2 Õ(1/ε 3 ) n O (1) for Maximum Clique on unit ball graphs, even without the geometric representation.

From Theorem 3, we also get an exact subexponential algorithm running in time 2 Õ(n 2/3 ) for Maximum Clique on unit ball graphs. Indeed, such an algorithm was obtained for the class of graphs G such that iocp(G) 1 [START_REF] Bonnet | QPTAS and subexponential algorithm for maximum clique on disk[END_REF].

In sharp contrast, we will prove that with an extra dimension or with different radii (even arbitrarily close to each other), a PTAS is highly unlikely. In both cases, we show that there is a constant ratio which is not attainable even in subexponential time, unless the ETH fails. A 2-subdivision of a simple graph is the graph obtained by subdividing each edge exactly twice. A co-2-subdivision is the complement graph of a 2-subdivision. The class of the 2-subdivisions (resp. co-2-subdivisions) is the set of all graphs that are the 2-subdivision (co-2-subdivision) of a simple graph.

The following result was shown by Bonnet et al.

Theorem 8 ([10]

). There is a constant α > 1 such that Maximum Clique on co-2subdivisions is not α-approximable even in time 2 n 0.99 , unless the ETH fails. Moreover, Maximum Clique is NP-hard on co-2-subdivisions.

Therefore, we just need to show that all co-2-subdivisions can be realized by our geometric objects. This appears like a simple and powerful method to rule out a PTAS (QPTAS, and even SUBEXPAS) for a geometric clique problem.

The co-2-subdivision of a graph with n vertices and m edges can be thought of as follows. It is made by a clique of n vertices representing the initial vertices, and a clique of 2m vertices minus a perfect matching; each anti-matched pair of vertices corresponding to an edge in the initial graph. Each vertex representing half an initial edge is adjacent to all the vertices representing the initial vertices but one.

Theorem 9. The class of 4-dimensional unit disks contains all the co-2-subdivisions.

Proof. Given any simple graph G = (V, E) with n vertices and m edges, we want to build a set S of n + 2m points in R 4 where each vertex v is represented by a point p(v) and each edge e, by two points p + (e) and p -(e). A pair of points in S should be at distance at most 2, except if it is the two points of the same edge e, or if it is a point p(v) with either a p + (vw) or a p -(wv); those pairs should be at distance strictly more than 2. We call x, y, z, t the coordinates of R 4 . Let P be the plane defined by the intersection of the hyperplanes of equation z = 0 and t = 0. The projection π onto P of the points p + (e) (resp. p -(e)) fall regularly on the "top" part (resp. "bottom" part) of a circle C of P centered at the origin O = (0, 0, 0, 0) and of diameter 2, such that for each edge e, π(p + (e)) and π(p -(e)) are antipodal on C. We just defined the points π(p + (e)) and π(p -(e)). The actual points p + (e) and p -(e) will be fixed later by moving them very slightly away from their projection in a two-dimensional plane orthogonal to P. Let η be the maximum distance between a pair (π(p + (e)), π(p -(e ))) with e = e . By construction η < 2.

Let P ⊥ be the (2-dimensional) plane containing the center O of C and orthogonal to P; in other words, the intersection of the hyperplanes of equation x = 0 and y = 0. We observe that all the points of P ⊥ are equidistant to all the points π(p + (e)) and π(p -(e)). We place all the points p(v) in P ⊥ regularly spaced on a arc of a circle lying on P ⊥ centered at O and of radius √ 3 -ε. One can notice that for any (v, e, s) ∈ V × E × {+, -}, d(p(v), π(p s (e))) = 4 -2 √ 3ε + ε 2 . We will choose ε 2 -η 1 so that this shared distance is just below 2 and the points {p + (e), p -(e)} e∈E realize the same adjacencies than their projection by π.

For every e = uv ∈ E, we place p + (e) such that ----------→ π(p + (e))p + (e) = - Corollary 10. There is a constant α > 1 such that Maximum Clique on 4-dimensional unit disks is not α-approximable even in time 2 n 0.99 , unless the ETH fails. Moreover, Maximum Clique is NP-hard on 4-dimensional unit disks.

The proof of Theorem 9 can be tweaked for balls of different radii. For a real ε > 0, we say that the radii of a representation (or the representation itself) are ε-close if the radii are all contained in the interval [1, 1 + ε]. We denote by B(1, 1 + ε) the ball graphs having an ε-close representation.

Theorem 11. For any ε > 0, the subclass of ball graphs B(1, 1 + ε) contains all the co-2-subdivisions.

Proof. Let x, y, z be the coordinates of R 3 . We start similarly and define the same π(p + (e)) and π(p -(e)) as in the previous construction for the points p + (e) and p -(e) on a circle C of diameter 2 centered at O = (0, 0, 0) on a plane P of equation z = 0. One difference is that π(p + (e)) and π(p -(e)) are no longer projections. We then place the points p(v) regularly spaced along the z-axis. More precisely, if the vertices are numbered v 1 , v 2 , . . . , v n , the position of p(v i ) is (0, 0, √ 3 + iε ). The radius of the disk representing v i centered at p(v i ) is set to r i := 1 + ( √ 3 + iε ) 2 -1 + ε . The radii associated to the centers p + (e) and p -(e) are all set to 1. We move p + (v i v j ) (resp. p -(v i v j )) away from π(p + (v i v j )) (resp. π(p -(v i v j ))) in the opposite direction of ---------→ p + (v i v j )p(v i ) (resp.

---------→ p -(v i v j )p(v j )) by an infinitesimal quantity, in order to only suppress the overlap of the disks centered at p + (v i v j ) and p(v i ) (resp. p -(v i v j ) and p(v j )). We make ε and ε small enough that all the values r i are between 1 and 1 + ε.

We call quasi unit ball graphs those graphs in the intersection ε>0 B(1, 1 + ε). As a corollary, we get some strong inapproximability even for quasi unit ball graphs.

Corollary 12.

There is a constant α > 1 such that Maximum Clique on quasi unit ball graphs is not α-approximable even in time 2 n 0.99 , unless the ETH fails. Moreover, Maximum Clique is NP-hard on quasi unit ball graphs.

Figure 2

 2 Figure 2The two cases for the collinear vectors -→ xix and -→ yjy.

Figure 3

 3 Figure 3The overall construction for 4-dimensional unit disks. We only represent the centers.

  |I| of the vertices. We can thus delete this layer, and note that connected components that do not contain C og are bipartite. We then focus on the component containing C og , which has only few layers. Secondly, we show that this component admits an odd-cycle transversal of size at most

	ε 2 |I| (informally, the neighborhood at distance up to O( 1 ε ) of O( 1 ε ) consecutive vertices
	on the cycle C og ).
	2 βε that
	contains at most εβ 2 n

ε 2

  By Claim 2, removing this S γ from H makes the graph bipartite. So, we do that and finally compute a maximum independent set in polynomial time in H -S γ . We return the best solution found. The pseudo-code is detailed in Algorithm 1.

			8 βε + 3 < g; a contradiction.
	We conclude that the 2-coloring is indeed proper.
	Since the sets of {S γ } γ∈[0, 2 βε ] are pairwise disjoint, a smallest set of the collection
	satisfies |S γ |	βε 2 n	ε 2 |I|.

The NP-hardness, ruling out a 1-approximation, is still to show.


Angélique Villière

Laurent Lethuaut

Catherine Fillonneau

Carole Prost

Selecting a representative

published or not. The documents may come

  Selecting a representative extraction method to analyze wine aroma The use of the InnOscent device enables to recover and compare the odor representativeness of various extracts in safe conditions, removing selectively solvent from those obtained by liquid-liquid extraction procedures. With a score of 7,4/10, the headspace SPME extraction with a Car/PDMS fiber and a 10 minutes extraction time was evidenced to be the most representative method among those evaluated. This method was then applied and GC-MS-O was performed to analyze the aroma profile of different wines through the Innovaroma project. IX th In Vino Analytica Scientia Symposium -Trento (Italy) -14-17 July 2015 Flavor team -GEPEA -UMR CNRS 6144The success of wine aroma characterization depends largely on the nature of the extract analyzed. Many extraction methods are currently performed before proceeding to wines' aroma analysis. The extraction step should produce extracts with aroma characteristics as close as possible to those of the corresponding product. However, the odor representativeness of the extract obtained is a criterion rarely taken into account.Regarding these considerations and using the InnOscent device, a relevant extraction method for wine aroma analysis was searched for on the basis of its odorant representativeness. This research was supported by the Bretagne and Pays de la Loire French councils within the framework of the INNOVAROMA project Extracts obtained by the different extraction methods were evaluated on the basis of their odor similarity with the odor of the wine headspace Liquid-liquid extraction (LLE) Stir Bar Sorptive Extraction (SBSE)angelique.villiere@oniris-nantes.fr


Waseem Al Hadad
email: waseem.al-hadad@univ-lorraine.fr

Denis Maillet

Yves Jannot

Vincent Schick

Inverse conduction and advection in a flat channel with transient external thermal excitation and observation

Keywords: conduction and advection, conjugate heat transfer, minichannel, unsteady heat transfer, convolution and deconvolution, inverse problems, measurement and instrumentation. Nomenclature channel length, m

The transient profiles of temperature and normal heat flux inside a flat minichannel heated by a surface heat source are constructed from temperature measurement over its external heated face. It uses analytical expressions of the corresponding transfer functions which are calculated using Laplace and Fourier integral transforms. Firstly, this estimation technique is verified on synthetic outputs of a finite elements code (COMSOL). Then it is implemented on an experimental minifluidic bench with electrical heating and temperature measurement by thermocouples and infrared thermography, for a low Péclet number of the flow. The presented results show that the heat source can be recovered at any time, as well as the internal normal heat flux and temperature distributions, including the bulk temperature of the liquid flow.

In our previous works, we have shown the interest of transfer functions for linear time invariant systems where heat diffusion and advection occur, both on a theoretical [START_REF] Hadad | Modeling unsteady diffusive and advective heat transfer for linear dynamical systems : A transfer function approach[END_REF] and on an experimental [START_REF] Hadad | Experimental transfer functions identification : Thermal impedance and transmittance in a channel heated by an upstream unsteady volumetric heat source[END_REF] basis. In this paper, which deals with a flat mini heat extractor, we will show how the surface heat source as well as the internal state variables (temperature and heat flux) can be estimated from temperature measurements over one of the outer faces using the correponding transfer function. This non-destructive estimation technique, that corresponds to the construction of a virtual sensor, allows us therefore to estimate, in steady and transient regimes, the thermal state at locations difficult to access using direct measurements at another easy to access location. This requires the system to be linear with a geometry, thermophysical properties and fluid velocities that do not vary with time.

So, the topic dealt with in this paper derives from the now classical Inverse Heat Conduction Problem (IHCP) introduced by J.V. Beck et al. in the 80's [START_REF] Beck | Inverse heat conduction : Ill-posed problems[END_REF] which consists in reconstructing surface temperatures or heat fluxes at part of the boundary of a solid domain, using known boundary conditions over its complementary part, the missing information being replaced by internal temperature measurements. This type of problem is mathematically ill-posed because the presence of noise in the data tends to make reconstruction of temperature or flux at the unknown part of the boundary unstable. This requires some special class of data processing called "regularization". This IHCP approach is very useful to estimate experimentally the distributions of both heat flux and temperature over the inner surface of the heated wall of a channel, using the diffusion heat equation in its solid volume, in order to derive the profiles of the internal convection coefficients. It can be used, for example, to optimize internal fluid mechanics in such a channel, see [START_REF] Tougri | Internal heat transfer coefficient estimation in three-dimensional ducts through the reciprocity functional approach-an analytical approach and validation with experimental data[END_REF].

In Inverse Forced Convection Problems (IFCP) [START_REF] Jarny | Inverse methods applied to forced convection in heat transfer[END_REF], the problem at stake is exactly the same, but the studied domain is a flowing fluid whose velocity field is known. The first works about this type of problems appeared in the 1990's and concerned estimation of inlet space [START_REF] Raghunath | Determining entrance conditions from downstream measurements[END_REF] or time [START_REF] Bokar | An inverse analysis for estimating the timevarying inlet temperature in laminar flow inside a parallel plate duct[END_REF] temperature distributions in a flat heated channel [START_REF] Raghunath | Determining entrance conditions from downstream measurements[END_REF] or the wall heat flux estimation in a flat [START_REF] Jarny | Inverse methods applied to forced convection in heat transfer[END_REF] [START_REF] Liu | Inverse analysis of transient turbulent forced convection inside parallelplate ducts[END_REF] or annular [START_REF] Li | Inverse convection problem for determining wall heat flux in annular duct flow[END_REF] channel in transient thermal regime.

The precise subject of our work is the Inverse Conjugate Forced Convection Problem (ICFCP) : the type of heat equation to be inverted is still the forced convection heat equation but it concerns not only a fluid, but also a solid subdomain, where a zero velocity field prevails, with the specific character that no heat transfer coefficient is used at their interface anymore. Few papers can be found yet for ICFCP, see [START_REF] Lin | Inverse problem of unsteady conjugated forced convection in parallel plate channels[END_REF] for example, since articles on the corresponding direct problem only date back to the early 2000's, see [START_REF] Herwig | Critical view on "new results in microfluid mechanics" : an example[END_REF] [12] [13] [START_REF] Vera | On the role of axial wall conduction in mini/micro counterflow heat exchangers[END_REF]. However, to our knowledge, no work on ICFCP can be found with inversion not only of simulated measurements but also of real ones.

Our paper is organized as follows : in section 2, we introduce the studied system (here the heat extractor) and its modelization. In section 3, we derive the methodology for estimating the internal conditions from measurements over one of the external faces as well as the corresponding transfer function in a mini-heat extractor. In section 4, we validate the methodology of sections 2 and 3 using synthetic profiles generated by COMSOL. In section 5, we apply this proposed methodology to a real experiment and will show the corresponding results.

2. The studied system and its transient modeling

The studied system

Let us consider a laminar fluid flow in a channel of length 2 , of thickness e f , limited by two parallel plates of polycarbonate of thicknesses e 1 and e 2 , see Figure 1. The velocity profile u(y) is assumed to be parabolic (Poiseuille flow) and fully developed from the inlet to the outlet of channel. The two solid layers (walls) and the fluid layer are characterized by their thermal conductivity λ i , their volumetric heat ρc i and their thermal diffusivity a i = λ i /ρc i where i = s 1 , s 2 or f respectively.

A surface heat source, q(x, t) is imposed between x 1 and x 2 on the lateral hot face noted here h. The two lateral faces (hot h and cold c) exchange heat with its surrounding environment (here ambient air) which is at an unifrom temperature T ∞ . These exchanges are characterized by coefficients h 1 and h 2 respectively. These ones are assumed to be uniform on each face (they integrate natural convection and linearized radiation).

x y

 +  - ∞ T 1 h ∞ T 1 s 2 s f e 1 e 2 e ) ( t x q , 2 h h wh wc c ( ) y u 1 x 2 x

Modelization

The heat equation describing 2D heat transfer in transient state in the walls (upper wall, s 1 and lower wall, s 2 ), in the fluid layer (f ) and the corresponding boundary and initial conditions, are :

• Heat equation in the solid (wall) :

∂ 2 T s i ∂x 2 + ∂ 2 T s i ∂y 2 = 1 a s i ∂T s i ∂t with i ≡ 1 or 2 (1)
• Heat equation in the fluid :

∂ 2 T f ∂x 2 + ∂ 2 T f ∂y 2 - u (y) a f ∂T f ∂x = 1 a f ∂T f ∂t (2)
• External in-plane boundary conditions :

ϕ h (x, t) = q(x, t) -h 1 (T -T ∞ ) at y = - e f 2 -e 1 (3)
ϕ c (x, t) = -h 2 (T -T ∞ ) at y = + e f 2 + e 2 (4)
where ϕ h (x, t) and ϕ c (c, t) are the heat fluxes in the y direction, on the h and c faces respectively. q is the surface density of the heat source power. We assume here that q(x, t) is separable and can be written as the product of a transient intensity

Q(t) (in W ) by a space distribution f (x) (in m -2 ) : q (x, t) = Q(t) f (x) (5)
• The solid/fluid interface conditions : at the solid/fluid interfaces, we assume the continuity conditions of heat flux and temperature :

-λ s i ∂T s i ∂y = -λ f ∂T f ∂y and T s i = T f at y = ± e f 2 (6)
where i ≡ 1 if y = -e f /2 and i ≡ 2 if y = +e f /2

• The axial boundary conditions are periodicity boundary conditions :

∂T i ∂x = 0 and T i = T ∞ at x = ±L for i ≡ s 1 , s 2 or f (7)
Here length 2L, with k v = L/ > 1, corresponds to the virtual length of the channel, see [START_REF] Hadad | Modeling unsteady diffusive and advective heat transfer for linear dynamical systems : A transfer function approach[END_REF].

• Initial condition : T | x,y,t=0 = T ∞ (8)
The developed parabolic velocity field u(y) within the flow can be made homogeneous through the parameterization of the fluid layer into K fluid layers of thicknesses e k = y k -y k-1 , with y 0 = -e f /2, see Figure 2. The exact velocity distribution u(y) and its parameterized distribution u k can be written as :

u (y) = 3 2 U m 1 -4 y e f 2 ⇒ u k = 3 2 U m 1 - 4K 3e 3 f y 3 k -y 3 k-1 (9)
where U m is average velocity and K is the number of fluid sublayers.

x y A change of function is made in order to define the temperature increase θ, that is the response to the surface heat source q(x, t) :

 +  - ∞ T 1 h ∞ T 1 s 2 s f e 1
θ(x, y, t) = T (x, y, t) -T ∞ (10)
The Laplace transform θ in time as well as the Fourier transform θ in axial direction of temperature increase θ for the [-L; +L] interval, are defined by :

θ (x, y, p) = ∞ 0 θ (x, y, t) e -pt dt (11) θn (y, t) = +L -L θ (x, y, t) e -ιαnx dx with ι 2 = -1 (12)
The discrete eigenvalues α n = nπ/L are defined here for any relative integer n. Fourier inversion of (12) requires a truncation to an even number N h = 2n h of harmonics, where n h is the number of harmonics of strictly positive order :

θ(x, y, t) ≡ 1 2L ∞ n=-∞ θn (y, t) e ιαnx ≈ 1 2L n h n=-n h +1 θn (y, t) e ιαnx (13)
After applying the Laplace and Fourier transformations to the solid and fluid heat equations ( 1) and ( 2) respectively, and by taking into account axial boundary conditions [START_REF] Bokar | An inverse analysis for estimating the timevarying inlet temperature in laminar flow inside a parallel plate duct[END_REF] as well as the initial condition (8), we get an ordinary differential equation in each domain :

In the walls :

d 2 θs in dy 2 -β 2 n θs in = 0 with β 2 n = (α 2 n + p a s i ) (14)
In each fluid layer :

d 2 θfn dy 2 -γ 2 k θfn = 0 with γ 2 k = (α 2 n + ι u k a f α n + p a f ) (15)
The transformed equations ( 14) and ( 15) apply for any point in the solid walls or in the fluid sublayer respectively. The interface conditions [START_REF] Raghunath | Determining entrance conditions from downstream measurements[END_REF] and the in-plane boundary conditions (3) and ( 4) are also transformed in the same way. We introduce φ, the Fourier and Laplace transform of the transverse heat flux ϕ (in y direction). So, integration of equations ( 14) and ( 15) leads to an analytical solution, in a quadrupolar form [START_REF] Maillet | Thermal quadrupoles : solving the heat equation through integral transforms[END_REF], of equations ( 1) to [START_REF] Liu | Inverse analysis of transient turbulent forced convection inside parallelplate ducts[END_REF] assuming the parameterization of the velocity distribution, which yields :

θn qn h = A n B n C n D n θn 0 c ( 16
)
where

A n B n C n D n = H 1 S 1n F n S 2n H 2 and F n = K k=1 F kn
where the indices h and c denote respectively the external faces.

H i = 1 0 h i 1 , S in = A in B in C in A in and F kn = A kn B kn C kn A kn A in = cosh (β n e i ), B in = sinh (β n e i ) /(λ s β n ) et C in = (λ s β n ) sinh (β n e i ), for i ≡ s 1 , s 2 . A kn = cosh (γ n e k ), B kn = sinh (γ n e k ) /(λ f γ n ) et C kn = (λ f γ n ) sinh (γ n e k ), for k = 1 to K.
The internal conditions on the wh and wc faces (see Figure 1) as well as on the interfaces between each sublayer k can be written as a function of the external c face :

Internal hot face (wh) :

θn φn wh = F n S 2n H 2 θn 0 c = A wh n B wh n C wh n D wh n θn 0 c (17)
Internal cold face (wc) :

θn φn wc = S 2n H 2 θn 0 c = A wc n B wc n C wc n D wc n θn 0 c (18)
Interfaces sublayers (k) :

θn φn k =   K k =k+1 F kn   S 2n H 2 θn 0 c = A k n B k n C k n D k n θn 0 c ( 19
)
From the temperature profiles in each sublayer, the bulk temperature profile can be calculated by :

θ b (x, t) ≡ 1 2 U m K K k=1 u k θ(x, y k , t) + θ(x, y k+1 , t) (20)

Estimation of internal conditions from measurements on external faces

The model [START_REF] Aster | Parameter estimation and inverse problems[END_REF][START_REF] Hansen | Truncated singular value decomposition solutions to discrete ill-posed problems with ill-determined numerical rank[END_REF][START_REF] Hadad | Regularization using truncated singular value decomposition for estimating the fourier spectrum of a noised space distribution over an extended support[END_REF][START_REF] Rouizi | Fluid temperature distribution inside a flat mini-channel : semi-analytical wall transfer functions and estimation from temperatures of external faces[END_REF] shows that it is sufficient to know the spectrum of the heat sources qn and the structural parameters (e 1 , e 2 , e f , U m , ...) in order to be able to retrieve the evolutions of temperatures and heat fluxes everywhere in the system. This formalism corresponds to the resolution of the direct problem.

In the problem of experimental estimation of internal conditions (temperatures and heat fluxes) from the measurements over the external faces, it is difficult to measure the heat source q(x, t). In heat transfer experiments, it is easier to measure temperature. The quadrupole model [START_REF] Aster | Parameter estimation and inverse problems[END_REF][START_REF] Hansen | Truncated singular value decomposition solutions to discrete ill-posed problems with ill-determined numerical rank[END_REF][START_REF] Hadad | Regularization using truncated singular value decomposition for estimating the fourier spectrum of a noised space distribution over an extended support[END_REF][START_REF] Rouizi | Fluid temperature distribution inside a flat mini-channel : semi-analytical wall transfer functions and estimation from temperatures of external faces[END_REF] shows that the internal conditions can be derived from the measurement of the temperature field over the hot face, θ h or over the cold face, θ c . In the mathematical sense, the best choice is to measure the temperature at the place where the signal-to-noise ratio is as large as possible, which is here the temperature over the hot face, θ h . Since the quadrupole model was written in the Laplace and Fourier domain, therefore the first step of the solution requires estimating the spectrum of experimental θ h .

Estimation of the Fourier spectrum of the front face temperature θ h for each time

The inverse Fourier transformation over the [-L; +L] interval (see [START_REF] Degiovanni | An alternative to heat transfer coefficient : A relevant model of heat transfer between a developed fluid flow and a non-isothermal wall in the transient regime[END_REF]), is written for the temperature increase of the front "hot" face θ h at the x i points of the [-; + ] interval, at any time t j :

θ h (x i , t j ) ≈ 1 2L n h n=-n h +1 θh n (t j ) e ιαnx i (21a)
This can be put under a column-vector/matrix form as θ h (t j ) = G θh (t j ), where θ h (t j ) is the vector gathering the theoretical noiseless values of the observed N x temperatures at a given time t j , θh (t j ) the spectrum vector composed of the N h harmonics used (N h ≤ N x ) at the same time, and G the N x × N h matrix formed with the e ιαnx i coefficients :

G ij = e ια -n h +j x i for i = 1 to N x and j = 1 to N h (21b)
The Fourier spectrum of the corresponding experimental profile θ exp h (t j ) can be estimated through a least squares minimization of :

θh (t j ) = arg min J θh (t j ) = (G * G) -1 G * θ exp h (t j ) where J θh (t j ) = r k ( θh (t j )) 2 with r k ( θh (t j )) = θ exp h (t j ) -G θh (t j ) ( 22
)
where θh is the ordinary least square estimate of θh , J the ordinary least squares sum, r k the residual vector at time t j , G * the conjugate transpose of complex matrix G. This can also be written using the Singular Matrix Decomposition (SVD) of matrix G, which is square if

N h = N x : θh (t j ) = V Σ -1 U * θ exp h (t j ) where G = U ΣV * (23)
where

Σ = diag (Σ 1 , Σ 2 , ..., Σ Nx ) Σ 1 Σ 2 ... Σ Nx-1 Σ Nx > 0 U * U = U U * = V V * = V * V = I Nx U = [U 1 , U 2 , ..., U Nx ] and V = [V 1 , V 2 , ..., V Nx ]
Here Σ is the diagonal matrix composed of the singular values Σ i of G (for i = 1 to N x ), U the matrix of its N x left singular (column) vectors U i and V the matrix of its N x right singular (column) vectors V i .

In the cas where the matrix to be inverted G or Σ is ill-conditioned (Σ 1 /Σ Nx >> 1), the experimental spectrum estimation using model [START_REF] Stehfest | Algorithm 368 : Numerical inversion of laplace transforms [d5[END_REF] or [START_REF] Stehfest | Remark on algorithm 368 : Numerical inversion of laplace transforms[END_REF] becomes unstable [START_REF] Beck | Inverse heat conduction : Ill-posed problems[END_REF]. To overcome this difficulty, that is to make this estimate stable, one has to regularize. In other words, one has to modify the matrix to be inverted to make it well conditioned [START_REF] Aster | Parameter estimation and inverse problems[END_REF]. Several regularization techniques exist. In this work only the Truncated Singular Value Decomposition (T SV D) technique [START_REF] Hansen | Truncated singular value decomposition solutions to discrete ill-posed problems with ill-determined numerical rank[END_REF][START_REF] Hadad | Regularization using truncated singular value decomposition for estimating the fourier spectrum of a noised space distribution over an extended support[END_REF][START_REF] Rouizi | Fluid temperature distribution inside a flat mini-channel : semi-analytical wall transfer functions and estimation from temperatures of external faces[END_REF][START_REF] Rouizi | Experimental assessment of the fluid bulk temperature profile in a mini channel through inversion of external surface temperature measurements[END_REF] is used. The T SV D as implied by its name, consists in truncating the smallest singular values that are responsible for high values of the condition number of G or Σ. The truncated version of this estimator is :

θh,α x (t j ) = V Σ -1 αx U * θ exp h (t j ) with Σ -1 αx = diag Σ -1 1 , Σ -1 2 , ..., Σ -1 αx , 0, ..., 0 (24)
where α x is the regularization parameter whose integer value can vary from 1 to N h . Between the two limits, there is an optimum which can be found using Morozov's discrepancy principle [START_REF] Aster | Parameter estimation and inverse problems[END_REF] or by the L-curve [START_REF] Hansen | Analysis of discrete ill-posed problems by means of the l-curve[END_REF]. Here Morozov's discrepancy principle is used. It consists to get a Root Mean Square Residual (RMSR) that cannot be lower than the measurement noise (level of residuals slightly higher than the measurement noise) :

RM SR(α x ) ≥ σ with RM SR(α x ) = r k ( θh,α x (t j )) T r k ( θh,α x (t j )) N x ( 25
)
where σ is the noise standard deviation.

Time inversion using regularized deconvolution of the Fourier harmonics of the front face temperature

Once the Fourier spectrum vector θh,αx (t j ), of size N h × 1, of the front face temperature θ h (t j ), has been estimated for each time t j = j t (for j = 1 to N t ), all the different harmonics can be recast into N h column-vectors θh n , of size N t × 1, whose components are equals to the TSVD estimation of θh n (t j ), as :

θh n = ˆ θ h n (t 1 ), ˆ θ h n (t 2 ), ..., ˆ θ h n (t Nt ) T (26)
Since the system of equations ( 1) to ( 8) is linear with time invariant coefficients, the simple product in the Laplace domain is a convolution product in the time domain. Using equations (16 to 19), the unknown spectrum of temperature or heat flux at a given face, let's call it ỹn here, can be calculated from the Fourier transform of front face temperature θh n as :

ỹn = Hn θh n (27a) =⇒ ỹn (t) = Hn (t) * θh n (t) (27b) = t 0 Hn (t -t ) θh n (t ) dt (27c)
where the star symbol ( * ) designates the convolution product in the time domain and Hn is the Fourier transform of the impulse response, that is the original of transfer function H(p). The latter can be called a transimttance, H ≡ W if the response corresponds to a temperature y ≡ θ and it is called an admittance, H ≡ Y if the response corresponds to a heat flux y

≡ ϕ [1] [2].
The convolution integral in equation (27c), is calculated through a numerical quadrature. This can be put under a column-vector/matrix form :

ŷn = M Hn θh n ( 28
)
where M (.) is a (square) matrix function of a column vector, here a lower triangular Toeplitz matrix based on the parameterization of a function on a basis of piecewise constant functions. It is defined as :

M (ψ) = t         ψ 1 0 0 • • • 0 ψ 2 ψ 1 0 . . . . . . ψ 3 ψ 2 ψ 1 . . . . . . . . . . . . . . . . . . . . . ψ Nt ψ Nt-1 ψ Nt-2 • • • ψ 1         with ψ =        ψ 1 ψ 2 ψ 3 . . . ψ Nt        (29)
where

ψ j = 1 t t j t j-1 ψ(t) dt 1 2 (ψ(t j-1 ) + ψ(t j )
) and t j = j t for j = 1 to N t and ψ(t 0 = 0) = 0. The temperture or heat flux profiles over a given face et at each time t j , can be calculated from its Fourier spectrum vector, see equations (21a and 21b) :

ŷ(t j ) = G ŷ(t j ) (30)
Let us note that the calculation of each harmonics of the internal and rear face temperature or heat flux (y ≡ θ wh , θ wc , θ k , θ c , ϕ wh or ϕ wc ) at any time, see (28), and hence its corresponding space profile, see (30), corresponds to the solution of a direct and well-posed problem (convolution problem). It is not the case for the heat source profile, q, estimation which corresponds to a deconvolution problem, see ( 16) :

qn = [K Nt ] -1 M H2 n θh n where K Nt = M H1 n (31) with H1 n (t) ≡ L -1 ( 1 C n ) and H2 n (t) ≡ L -1 ( 1 A n )
where L -1 is the inverse Laplace transform, which can be calculated numerically by Stehfest's algorithm [START_REF] Stehfest | Algorithm 368 : Numerical inversion of laplace transforms [d5[END_REF][START_REF] Stehfest | Remark on algorithm 368 : Numerical inversion of laplace transforms[END_REF]. Since the measured temperature θ h is noisy, the heat source estimation, see ( 31) is an ill-posed problem. In this case, a time regularization by T SV D is possible :

qn = K † αt M H2 n θh n (32)
with

K † αt = V Σ -1 αt U * where K Nt = M H1 n = U Σ Nt V *
where K † αt is the pseudo-inverse of K Nt , obtained by its T SV D form above, keeping α t singular values. α t is hyper-parameter corresponding to the temporal T SV D regularization. The temperatures, heat flux and corresponding heat source, can be estimated from the information on the external face θ h as listed in (Table 1).

W wh n (t) = L -1 (A wh n /A n ) (16
) and ( 17)

θwh n (t) = W wh n (t) * θh n (t) convolution θwc W wc n (t) = L -1 (A wc n /A n ) (16
) and ( 18)

θwc n (t) = W wc n (t) * θh n (t) convolution θk W k n (t) = L -1 (A k n /A n ) (16
) and ( 19)

θk n (t) = W k n (t) * θh n (t) convolution θc W c n (t) = L -1 (1/A n ) (16)
θc n (t) = W c n (t) * θh n (t) convolution φwh Y wh n (t) = L -1 (C wh n /A n ) (16
) and ( 17)

φwh n (t) = Y wh n (t) * θh n (t) convolution φwc Y wc n (t) = L -1 (C wc n /A n ) (16
) and ( 18)

φwc n (t) = Y wc n (t) * θh n (t) convolution qh Y h n (t) = L -1 (1/A n ), Z h n (t) = L -1 (1/C n ) (16)
Y h n (t) * θh n (t) = Z h n (t) * qh n (t) deconvolution φh -- (3)
φh (x, t) = qh (x, t) -h

Results of the validation of the estimation technique on synthetic profiles

The system presented above, see section (2.1) was simulated here by COMSOL [24]. The temperature responses on the front, rear and internes faces (θ h , θ c , θ wh and θ wc respectively) correponding to surface heat source q(x, t) were calculated at each time t j where j = 1 to N t with N t = t f / t, where N t is observation number and t is the time step .In this simulation, we take t = 1 s and N t = 500. The simulation parameters are given in Table 2 and Table 3. Grid independence tests have been performed using several grid densities. In the present study triangular elements were used with 2152 degrees of freedom. The surface heat source q(x, t) has been assumed separable and uniform in space between x 1 and x 2 here. So it can be written as :

q (x, t) = Q(t) [H (x -x 1 ) -H (x -x 2 )] 1 S ( 33
)
where Q(t) is the time distribution of q (x, t) over a surface S, here a rectangular surface of length

x 2 -x 1 . Here Q(t) is a step function with Q(t < 0) = 0
and Q(t ≥ 0) = Q ss where ss designates the steady state. H designates the Heaviside function. The initial temperature T (x, y, t ≤ 0) of the system is assumed to be uniform and equal to the ambient temperature T ∞ = 20 • C. The lateral heat loss coefficient is taken here uniform (h 1 = h 2 = 10 W.m -2 .K -1 ).

The steady state surface heat source is set to q ss (x) = 400 W.m -2 .The corresponding average velocity U m , Reynolds number Re and the Péclet number P e are given in Table 4. Let us note that the Péclet number, P e, is equal to 1.4, which means that neither diffusion nor axial advection can be neglected in the heat equation for the fluid.

λ s λ f ρc s ρc f ν f (W.m -1 .K -1 ) (W.m -1 .K -1 ) (kJ.m -3 .K -1 ) (kJ.m -3 .K -1 ) (m 2 .s -1 ) 0.215 0.63 1440 4186 1.10 -6
The exact front face temperature profile at each time t j obtained by COMSOL θ exact h (t j ) is considered here as an experimental profile (noisy profile) after adding an independent identically distributed noise ε characterized Table 3: Standard geometrical parameters.

2 K v x 1 x 2 e 1 = e 2 = 2e f K N x = N h (mm) -(mm) (mm) (mm) - - 65
θ exp h (t j ) = θ exact h (t j ) + ε (34)
Using this noised "experimental" profile θ exp h (t j ) and the inversion technique presented in section (3), the internal, bulk and rear face temperature profiles are estimated. The experimental (from the numerical experiment) and estimated temperature profiles are presented successively. The experimental and recalculated front face temperature, T h is shown in Figure 3, the exact and estimated internal hot face temperature, T wh in Figure 4, the exact and estimated bulk temperature, T b in Figure 5, the exact and estimated internal cold face temperature, T wc in Figure 6 and finally the exact and estimated rear (cold) face temperature, T c in Figure 7. The profiles are represented at times t = 80, 240, and 400s. It is clear that there is a very good correlation between the exact temperature profiles obtained by COMSOL (direct problem) and their estimated counterparts obtained in a semi-analytical way using adhoc transfer functions (inverse problem).

The heat source as well as hot face flux are also estimated in the same way. The heat source and of its exact distribution, q is shown in Figure 8 and the estimated external hot face flux ϕ h is shown in Figure 9. Figure 8 shows that the heat source can be estimated fairly accurately (spatial door function with intensity of 400 W.m -2 ) whatever the considered time. The spatial and temporal regularization hyperparameters of each estimation (α x for recalculated T h and α t for q h ) are indicated in the legend of the corres-ponding figures. The obtained results are encouraging, allowing us to apply this method of inversion to real measurements, as can be seen in the next section.

Results of experimental estimation

Experimental setup

A sketch of the cross section of the channel is presented in Figure 10. The bench is composed of two polycarbonate (conductivity λ s , volumetric heat ρc s ) plates that are the outer walls of a three-layer system (thicknesses e 1 Figure 8: Exact (dotted lines) and estimated (full lines) front face heat source q(x, t) at times t = 80s (red), 240s (bleu) and 400s (green) (α t = 490 for N t = 500). and e 2 for the front and rear walls). The constant cross section of the channel is equal to we f , where e f is its thickness and w its width in the dimension normal to this figure. Two plenum chambers of larger thicknesses are located upstream and downstream the constant section channel. The total length of the channel, which corresponds to the distance between these two chambers is 2 c , while its length with the above defined constant thicknesses of its two walls is 2 .

IHTC15-9190

2 water/solid heat transfer coefficient and taking axial diffusion in both fluid and solid into account [START_REF] Raghunath | Determining entrance conditions from downstream measurements[END_REF][START_REF] Bokar | An inverse analysis for estimating the timevarying inlet temperature in laminar flow inside a parallel plate duct[END_REF]. Comparison of the output of these simulations with the corresponding output of a commercial finite elements code allows a verification of the quality of our semi-analytical model. Since the quadrupolar model used here yields explicit solutions for both temperature and flux at any point of the system, the first inverse problem met consists in estimating the Fourier spectrum of the recorded temperature fields over any one of the external faces at any time after the start of heating. This inversion, using here the recorded front face temperature profile at a given time, is based on the Singular Values Decomposition (SVD) of the square matrix connecting the measured temperature vector at the different pixels to its corresponding spectrum vector at the different space frequencies. So, Truncated SVD (TSVD) [START_REF] Liu | Inverse analysis of transient turbulent forced convection inside parallelplate ducts[END_REF] is implemented as a regularization method here.

Once the Fourier spectrum of the measured front face temperature distribution has been recovered at any time, several direct or inverse problems based on convolution or deconvolution with analytical transfer functions in Laplace domain are solved. This includes construction of the temperature and fluxes distributions at the inner wall/fluid flow interfaces (a deconvolution problem for each harmonics). These transient inversions are also made through the TSVD technique and the internal bulk temperature distribution is reconstructed at any time. The corresponding experimental inversions show that estimation of the internal temperature/flux distribution is possible and that a thermal balance allows the reconstruction of the transient bulk flow distribution for a Péclet number close to unity as well as the distribution of the surface heat source.

EXPERIMENTAL SETUP

A sketch of the cross section of the channel is presented in Fig. 1. The bench is composed of two polycarbonate (conductivity s λ , volumetric heat s ρc ) plates which form the outer walls of a three-layer system (thicknesses 1 e and 2 e for the front and rear walls). The constant cross section of the channel is equal to f we , where f e is its thickness and w its width in the dimension normal to this figure. Two plenum chambers of larger thickness are located upstream and downstream the constant section channel. The total length of the channel, which corresponds to the distance between these two chambers is c  2 , while its length with the above defined constant thicknesses of its two walls is  2 .

Fig. 1 Sketch of polycarbonate channel.

The liquid (de-ionized and deaerated water, conductivity f λ , volumetric heat f ρc ) is fed through the setup by a serynge pump with a constant average velocity U and the temperature in T of the water in the upstream plenum (tranquilization chamber) is adjusted thanks to the set point temperature of the thermostat that is adjusted in order to get a water inlet temperature

∞ = T T in
, where ∞ T is the temperature of the outside environment (air and walls of the lab), see Fig. 2 (right). The liquid (de-ionized and deaerated water, conductivity λ f , volumetric heat ρc f ) is fed through the setup by a serynge pump with a constant average velocity U m and the temperature T in of the water in the upstream plenum (tranquilization chamber) is adjusted thanks to the set point temperature of the thermostat that is adjusted in order to get a water inlet temperature T in = T ∞ , where T ∞ is the temperature of the outside environment (air and walls of the lab), see Figure 11.

The heating system, whose electrical power (tension V and current I) is recorded, is detailed in Figure 12a (left) : it is composed of a rectangular foil heating resistance, of area equal to w h , which is separated from the front face of the channel by a copper bar, of length w and cross section e h h , with a thermocouple set at its center. In order to have a low contact resistance between the copper bar and the channel front face, a 25µm thick of indium foil is set in between. Prior to heating, the syringe pump is activated during a time long enough in order to get the front face temperature monitored by the infrared camera, uniform and equal to T ∞ . So the incoming liquid temperature, the ambient temperature and the temperature field in the whole system are initially equal, which means that the temperature rise wherever in the system will be caused by Joule effect only. Pictures of the channel as well as of the whole setup are shown in Figure 13. The different geometrical and thermopysical parameters of the system are given in Table 5 and Table 6 respectively. The heating system, whose electrical power (tension V and current I ) is recorded, is detailed in Fig. 2 (left): it is composed of a rectangular foil heating resistance, of area equal to h w , which is separated from the front face of the channel by a copper bar, of length w and cross section h h e  , with a thermocouple set at its center. In order to have a low contact resistance between the copper bar and the channel front face, a 25 µm thick Indium foil is set in between. Prior to heating, the syringe pump is activated during a time long enough in order to get either the front face or the rear face temperature 0 T , monitored by the infrared camera, uniform and equal to in T . So the incoming liquid temperature, the ambient temperature and the temperature field in the whole system are initially equal, which means that the temperature rise wherever in the system will be caused by Joule effect only. Pictures of the channel as well as on the whole setup are shown in Fig. 3. The different geometrical and thermopysical parameters of the system are given in Table 1.

Heating system

λ s ρc s λ f ρc f (W.m -1 .K -1 ) (kJ.m -3 .K -1 ) (W.m -1 .K -1 ) (kJ.m -3 .K -1 )
0.215 1440 0.63 4186

Front face temperature measurement and preprocessing

For an imposed average water velocity U m = 10 -4 m.s -1 (P e = 1.4), the temperature field over the hot (front) face, θ h (x, t) is measured either by the thermocouple located inside the copper bar over the heating length h , or by an infrared camera focused on the external (front) surface of the channel right after the initial time when electrical heating starts until t f = 2400 s. A time average of 5 frames, which are acquired with a period of 0.2s, followed by a space averaging of the thermographic signal over 5 columns of pixels in the x direction is made, which result in the measurement of a x-temperature profile with a period t = 1s, which is the same as the acquisition time step of the thermocouple located inside the copper bar, see Figure 11. The infrared plane array InSb camera FLIR-Cedip Jade II works in the 3.5-5.6mm spectral interval. The temperature of the surrounding radiative environment is supposed to be equal to T ∞ . The uniform temperature of the copper bar is distributed over ficticious "pixels" of the same space step x as the pixels measured by the infrared camera. Because of the thickness of the heating assembly, see Figure 11 and Figure 13, and of the space transfer function of the camera which acts as a low pass filter (about 5 pixels are necessary to grasp a sharp temperature transition), the pixels in the vicinity of the copper bar cannot be measured and are replaced by a linear interpolation between the copper temperature and the recorded temperature beyond this 5 pixels interval.

Experimental results

We present in Figure 14 the measured and recalculated hot front face temperature only at times 80, 400, 800, 1200 and 1600 seconds past the start of the electrical step excitation. The chosen time step is t = 4 t = 4s and TSVD regularization has been implemented for the N x = 250 pixels of the front face temperature over the ] -; + ] interval and for L = 2 in order to estimate the N h = N x harmonics of the front face temperature spectrum with only α x = 130 singular values. The estimated hot interface temperature T wh , the estimated bulk temperature T b , the estimated cold interface temperature T wc as well as the estimated rear face temperature T c are plotted respectively in Figure 15 to Figure 17. We can see that the reconstruction of the front face temperature, see Figure 14, is very good. In Figure 15 to Figure 17, at short times, we can see the symmetry with respect to the heating interval, with a downstream shift for longer times because of advection. One can notice the start of a steep decrease of the temperature distributions, for the longer times, in the downstream regions : this is due to the change of thickness of the front and rear walls in this region. In the downstream region, we can also see that we have T b > T wh and T b > T wc past the heating stop : this can be explained by the fact that the thermal diffusivity of fluid a f is slightly higher than that of walls a s i and that P e > 1.

As shown in section 4, the surface heat source can be estimated by the technique proposed in this paper. In Figure 18 the estimated heat source is presented. In this experience, the surface heat source has been imposed electrically as a step function in time : the delay between the times t = 80 s and t = 1600 s can be explained by the thermal inertia of the heating system. The maximum is close to 500 W.m -2 for the last time shown (1600 s "steady state"), with an average value over the heating interval lower than 400 W.m -2 : it is coherent with the measured electrical power density of 405 W.m -2 over the same time interval. The difference stems from the heat losses towards the insulating material at the back of the heating resistance and from the heat losses of the lateral surface of the copper bar, which are not taken into account in the model. So, the source q that is estimated here and shown in Figure 18 is just an equivanent one. Hence, it is interested to estimate also the flux ϕ h entering the external face of the hot face wall, see Figure 19, and compare it to its counterpart shown in Figure 9 and estimated from simulated hot face temperature measurements. One can notice in Figure 9 larger oscillations near the boundaries of the channel than in Figure 19, where the signal over noise ratios were about the same in the simulated and real experiments. This difference stems from the abrupt variation of the source of ϕ h in the simulated experiement (a Heaviside function for the source q) for short times, while the prsence of the heating device shown in Figure 12, which is not modelled, allowed a continuous variation of flux ϕ h in the real experiment, with a lot easier regularization that prevented large Gibbs phenomena at the two boundaries of the channel.

Other interesting information that can be derived are space distributions of the internal heat fluxes ϕ wh and ϕ wc . In Figure 20, the estimated hot interface heat flux ϕ wh is presented. It is interesting to note that the heated fluid gives heat back to the wall past the heating region (negative flux). In Figure 21 the estimated cold interface heat flux ϕ wc is presented. Another non obvious effect can be found in this figure : the fluid upstream the heating region is colder than the cold wall, which means that this rear wall gives heat to the fluid (negative flux). The external cold heat flux, ϕ c is not shown here : it is proportional to the temperature variation of the cold face whose estimate is shown in Figure 17, which can be calculated as : ϕ c (x, t) = -h 2 (T c (x, t) -T ∞ ), (see equation 4).

Conclusion

We have shown that in a mini heat extractor the heat source, as well as the internal normal heat flux and temperature distributions, including the bulk temperature of the liquid flow, can be estimated at any time from external mesurements using a non intrusive inverse technique and a semi-analytical model. This stems from the existence of analytical transfer functions in the double transformed domain, that is Laplace in time and Fourier in space, in the direction x of the flow. This has also required the implementation of a numerical Laplace inversion algorithm, to make convolution products in time appear between Fourier harmonics of instantaneous x distributions of the different quantities.

As in our previous work [START_REF] Hadad | Experimental transfer functions identification : Thermal impedance and transmittance in a channel heated by an upstream unsteady volumetric heat source[END_REF] where an instantaneous temperature response, at a given point of a channel, to an upstream thermal power excitation in the fluid, was explained by an impedance Z involved in a convolution product, such can also be the case here. For example, the corresponding relationship between the intensity Q(t) of the heating power and its point response at a point x of the cold face is given by :

θ c (x, t) = Z c (x, t) * Q(t) (35a)
where

Z c (x, t) = 1 2L n h n=-n h +1 Zc n (t) e ιαnx with Zc n (t) = L -1 1 C n (p) (35b)
These analytical functions are available here because of the simple geometry of the channel that makes the use of the Quadrupole method possible. For a complexe system (ex : heat exchanger with fins, turbulent, rough walls, ...), it can be identified by a calibration experiment [START_REF] Hadad | Experimental transfer functions identification : Thermal impedance and transmittance in a channel heated by an upstream unsteady volumetric heat source[END_REF]. Let us also note, that transfer functions, once known (model reduction or experiemental identification) are alternatives to the classical detailed modelling which sometimes requires large calculation times and memory, especially in transient simulation. Let us remark here that in this work, the input of the inverse problem is the measured instantaneous temperature distribution over the front face, that is the face that is heated. This implies of course the implementation of some kind of space regularization to recover its Fourier spectrum and some time regularization to estimate the history of each harmonics of any of the quantities (temperture, heat fluxes or heat sources, see left column of Table 1) that are looked for. However, we are in a favorable configuration because the front face temperature measurements is characterized by the presence of high space frequencies, which explains the low levels of the estimation errors shown in Figure 4 to Figure 8. Had the rear face temperature been measured, instead of the front one, the corresponding estimations would not have been as good, because of the necessary inversion of a temperature signal where high frequencies of the front face excitation have been damped by the solid walls and flowing fluid (low pass filter).

1 p 1 ν kinematic viscosity, m 2 .s - 1 Φ 3 ϕ

 11213 velocity, m.s -1 x, y spatial coordinates, m a thermal diffusivity,m 2 .s -Laplace eigenvalue of order n λ thermal conductivity, W.m -1 .K -heat flow rate (surface integral of ϕ), W ρ density, kg.m -heat flux density in y direction, W.m -2

Figure 1 :

 1 Figure 1: 2D model of flow and heat transfer in the flat channel.

Figure 2 :

 2 Figure 2: Parameterization of u(y) into a piecewise constant function with K = 5 parameters.

Figure 3 :

 3 Figure 3: Noised "experimental" (full lines) and recalculated (symbols and dots) front face temperature T h (x, t) at times t = 80, 240 and 400s (α x = 310 for N x = 600).

Figure 4 :

 4 Figure 4: Exact (full lines) and estimated (symbols and dots) internal hot face temperature T wh (x, t) at times t = 80, 240 and 400s.

Figure 5 :

 5 Figure 5: Exact (full lines) and estimated (symbols and dots) bulk temperature T b (x, t) at times t = 80, 240 and 400s.

Figure 6 :

 6 Figure 6: Exact (full lines) and estimated (symbols and dots) internal cold face temperature T wc (x, t) at times t = 80, 240 and 400s.

Figure 7 :

 7 Figure 7: Exact (full lines) and estimated (symbols and dots) rear (cold) face temperature T c (x, t) at times t = 80, 240 and 400s.

2 )Figure 9 :

 29 Figure 9: Estimated front face flux distributions ϕ h (x, t) at times t = 80s (red), 240s (bleu) and 400s (green).

Figure 10 :

 10 Figure 10: Sketch of polycarbonate channel.

Figure 11 :

 11 Figure 11: Mini channel with hydraulic circuit, infrared and thermocouple.

Figure 12 :

 12 Figure 12: Detail of heating system.

3

 3

Fig. 2

 2 Fig. 2 Mini channel with hydraulic circuit, and infrared and thermocouple temperature measurement and detail of heating system.

Fig. 3

 3 Fig. 3 Mini channel with hydraulic circuit, and surface heat source.

Figure 13 :

 13 Figure 13: Mini channel with hydraulic circuit, and surface heat source..

Figure 14 :Figure 15 :Figure 16 :Figure 17 :

 14151617 Figure 14: Hot front face temperature T h profiles (measured "full lines" and recalculated "circle" with α x = 130 for N x = 250).

Figure 18 :

 18 Figure18: Estimated surface heat source q (deconvolution, α t = 599 for N t = 600) profiles.

Figure 19 :Figure 20 :Figure 21 :

 192021 Figure 19: Estimated front face heat flux ϕ h profiles.

Table 1 :

 1 Temperatures, heat flux and heat source estimation using front face temperature measurement

		Transfer function H
	θ h .	unknown

n Equation Model and unknown Nature θwh

Table 2 :

 2 Standard thermophysical parameters.

Table 4 :

 4 The average velocity and corresponding dimensionless numbers.U m (m.s -1 ) Re = 2U m e f /ν f P e = 2U m e f /a f

	2	-6	6	2	5	600
	10 -4		0.2		1.4
	by a standard deviation (σ noise = 0.03

• C) for N x equidistant points on the interval [-; + ] of the front face :

Table 5 :

 5 Geometrical parameters.

	e 1 = e 2 (mm) e f (mm) 2 (mm) 2 c (mm) w(mm) h (mm)
	2	1	65	120	50	10

Table 6 :

 6 Thermopysical parameters.

θh (x, t) difference in (x, t) domain

Acknowledgment

We thank Jamal Ouhajjou and Franck Demeurie for their involvement in the realization and optimization of the experimental setup.