Alexandre Gondran
email: alexandre.gondran@enac.fr

Vincent Duchamp
email: vincent.duchamp@alumni.enac.fr

Laurent Moalic
email: laurent.moalic@uha.fr

Lower Bound for (Sum) Coloring Problem

The Minimum Sum Coloring Problem is a variant of the Graph Vertex Coloring Problem, for which each color has a weight. This paper presents a new way to find a lower bound of this problem, based on a relaxation into an integer partition problem with additional constraints. We improve the lower bound for 18 graphs of standard benchmark DIMACS, and prove the optimal value for 4 graphs by reaching their known upper bound.

Introduction

The Minimum Sum Coloring Problem M SCP is a variant of the Graph Vertex Coloring Problem (GVCP), with weights associated to colors. This problem can be applied to various domains such as scheduling, resource allocation or VLSI design [START_REF] Malafiejski | Sum coloring of graphs[END_REF][START_REF] Kubale | Graph Colorings[END_REF].

Given an undirected graph G = (V, E) with V a set of n vertices and E ⊂ V 2 a set of edges, graph vertex coloring involves assigning each vertex with a color so that two adjacent vertices (linked by an edge) feature different colors. An equivalent formulation is to consider a coloring as a partition of G into subsets of vertices so that two adjacent vertices not belong to the same subset [START_REF] Wu | Minimum sum coloring for large graphs with extraction and backward expansion search[END_REF].

The GVCP consists in finding the minimum number of colors (or equivalently the minimum number of subsets), called chromatic number χ(G), required to color (or equivalently to partition) the graph G.

The MSCP is a variant of GVCP, in which each color has a cost equals to the integer that represents the color. The objective of MSCP is to minimize the sum of the cost of the coloring, called chromatic sum of G and denoted Σ(G). Figure 1 gives an example of MSCP from Jin and Hao [START_REF] Jin | Hybrid evolutionary search for the minimum sum coloring problem of graphs[END_REF] on a graph with n = 9 vertices and shows the difference between the two problems. [START_REF] Jin | Hybrid evolutionary search for the minimum sum coloring problem of graphs[END_REF]. The left coloring uses 3 colors (integers 1, 2 and 3).

It is an optimal solution of GVCP and the chromatic number χ(G) = 3. Moreover, its sum coloring cost is equal to 18. The right coloring uses one more color (integers 1, 2, 3 and 4) but its sum coloring cost is equal to 15, which is the chromatic sum of G: Σ(G) = 15.

More precisely, one possible formulation of the MSCP is the following :

(M SCP )                      Min. fΣ(V) = n l=1 l|V l | (1)
s.c.

∪ l=1..n V l = V (2) V l ∩ V k = ∅, ∀(l, k), l = k (3) |V l | ≥ |V l+1 |, ∀l = 1..n -1 (4) {i, j} V l , ∀(i, j) ∈ E, ∀l = 1..n (5) V l ⊂ V ∀l = 1..n (6)
We denoted V = (V1, V2..., Vn) the partition of G (constraints (2) and ( 3)) into n sets with n, the number of vertices of G. For all 1 ≤ i ≤ n, each Vi is called color class. To be as general as possible, we do not precise the number k of colors used, we only know that 1 ≤ k ≤ n. Then the number of colors used in a coloring is equal to the number of none empty color classes : k = |{Vi ∈ V | |Vi| ≥ 1}|. Constraint [START_REF] Kubicka | Approximation algorithms for the chromatic sum[END_REF] indicates that two adjacent vertices cannot be in the same color class. That is the coloring constraint. Constraint (4) forces the color classes to be ordered from the largest to the smallest size. With this convention, the objective function can be expressed as equation ( 1). An optimal sum coloring of graph G, noted V * , has its objective function equals to the chromatic sum: fΣ(V * ) = Σ(G).

M SCP is an NP-hard problem [START_REF] Kubicka | Approximation algorithms for the chromatic sum[END_REF] and exact methods to solve it are effective only on small instances or specific graphs. For general graphs, we use heuristics to get a sub-optimal solution [START_REF] Jin | Algorithms for the minimum sum coloring problem: a review[END_REF]. It provides an upper bound of the optimal solution. We can compare it to a lower bound to estimate the quality of the solution.

This paper presents a new way to find lower bounds for this problem. We obtain it by relaxing MSCP into an Integer Partition Problem (IPP). A similar approach has recently be use by Lecat, Lucet and Li [START_REF] Lecat | New Lower Bound for the Minimum Sum Coloring Problem[END_REF]. They find a lower bound, called LBM Σ, using the notion of motif that improve largely the best lower bound of the literature (DIMACS benchmarks [START_REF]Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge[END_REF]). This paper improves this lower bound by counting the maximal number of independent sets of maximal size in a graph. An Independent Set (IS) or stable set is a set of vertices of G, no two of which are adjacent. A color class is by definition an IS. Others approaches designed to find the lower bound for M SCP are proposed in [START_REF] Wu | Minimum sum coloring for large graphs with extraction and backward expansion search[END_REF][START_REF] Jin | Hybrid evolutionary search for the minimum sum coloring problem of graphs[END_REF][START_REF] Wu | Improved lower bounds for sum coloring via clique decomposition[END_REF].

Experiments on standard benchmarks DIMACS [START_REF]Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge[END_REF] of graph instances show that we improve the lower bound for several graphs and we sometimes prove their optimal value by reaching their known upper bound.

In the following sections, we first present how we relax M SCP to an IP P (Section 2). In Section 3, we detail a new way of ordering integer partitions, and we use it to solve exactly our relaxed problem. Section 4 shows how to extend this lower bound to GVCP. We show and analyze our results in Section 5, and then we conclude.

Relaxation as an integer partition problem 2.1 Integer partitions

We relax the problem of sum coloring M SCP into a problem of integer partition, denoted IP PΣM , with the same objective function but with less constraints.

An integer partition is a way of writing a positive integer n as a sum of other positive integers. We say that the vector a = (ai) 1≤i≤n ∈ N n is a partition of n if :

(IP )      n i=1 ai = n ai ≥ ai+1, ∀i = 1..n -1
We arbitrarily choose to rank ai in decreasing order. Partitions can be graphically visualized with Young diagrams [START_REF] Young | On quantitative substitutional analysis[END_REF] or Ferrer diagrams. Figure 2 represents the partition of the integer 12 = 4 + 4 + 3 + 1 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0. The vector of this partition is: a = (4, 4, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0) or simply noted a = (4, 4, 3, 1) because the two first lines have four squares, the third line, three squares and the last one, one square.

Definition of IP P ΣM

Instead of considering a set partition (or equivalently vertices partition), we focus on the cardinality of each set and we study an integer partition of the number n = |V |, corresponding to the number of vertices. We note for each vertices set Vi, its cardinality ai = |Vi|. The objective function (1) of M SCP becomes n i=1 iai. By this way, the two first constraints of M SCP (constraints (2) and ( 3)) imply n i=1 ai = n. Constraint (4) of M SCP is still valid with the new notations: ai ≥ ai+1. We represent a coloring with Young diagram where each square represents a vertex. The number of color used is the number of lines. Squares in the same line are in the same color class. Figure 3 represents Young diagrams of the two colorings presented in Figure 1. Squares on the same line share the same color. The objective function value of M SCP is calculated by counting the number of squares for each line:

n i=1 iai.
The stability number of G, noted α(G), is the size of the maximum IS. It indicates the maximum number of columns of a Young diagram that it is possible to use for a coloring, therefore ai ≤ α(G). Moreover, we will define m as an upper bound of the maximum number of color classes of size α(G) which can be in a coloring. Then, we can add an extra constraint : |{ai|ai = α(G)}| ≤ m or equivalently if m < n to am+1 ≤ α(G) -1. Finding α(G) is a NP-hard problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of N P-Completeness[END_REF] and counting all maximal IS is #-P complete [START_REF] Valiant | The complexity of enumeration and reliability problems[END_REF]. Therefore, there are no polynomial-time algorithm able to solve these problems, unless P = N P . However, the graph size for which it is possible to solve them exactly in a reasonable time (less a few minutes) is around 1000 vertices for random graphs with 0.5 density by running a solver such as MoMC [START_REF] Li | On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem[END_REF], the state-of-art exact maximum clique algorithm. We define α an upper bound of α(G), for which the above constraints are still true: ai ≤ α and |{ai|ai = α}| ≤ m. If MoMC takes too much time to compute α(G), then a possible upper bound of the largest IS size, α, is the highest positive integer, k, verifying:

|{v ∈ V, d G [v] ≥ k}| ≥ k with d G [v] the degree of the vertex v in G, the complement graph of G 1 .
Another upper bound is the number of colors used for a vertex coloring of G not necessarily optimal.

The chromatic strength of a graph G, noted s(G), is the minimum number of colors used in all the optimal colorings of M SCP . It indicates the minimum number of lines of a Young diagram that are needed for a coloring. We note s a lower bound of s(G) and we notice that :

s(G) ≥ χ(G) ≥ n α(G) (7)
Indeed the chromatic number χ(G) is at least a lower bound of s(G) because an optimal coloring of M SCP is at least a legal coloring for GVCP. Moreover, a simple lower bound of χ(G)

is n α(G)
or at least n α . The number of coefficients of a not null (or equivalently the number of lines of Young diagram) is at least higher than s(G) and therefore higher than s, i.e. |{ai|ai ≥ 1}| ≥ s or equivalently as ≥ 1 because (ai) is a decreasing suite of integer.

Given a graph G = (V, E), knowing n = |V | its size, α an upper bound of its stability number, s a lower bound of its chromatic strength and m, an upper bound of the maximum number of color classes of size α, we define IP PΣM problem as:

(IP PΣM )                                Min. fΣM (a) = n i=1 iai (8)
s.c.

n i=1 ai = n (9) ai ≥ ai+1, ∀i = 1..n -1 (10) ai ≤ α, ∀i = 1..n (11) |{ai|ai = α}| ≤ m (12) as ≥ 1 (13) a = (ai) 1≤i≤n ∈ N n (14)
IP PΣM depends only of four integers: n, α, s and m. We denote ΣM the optimal objective function value of one of its optimal partition, a * : fΣM (a * ) = ΣM . Therefore, ΣM is function of these four parameters: ΣM (n, α, s, m).

Theorem 1. IP PΣM is a relaxation of M SCP , that is, ΣM (n, α, s, m) is a lower bound of Σ(G): ΣM ≤ Σ(G) (15)
Proof 1. The fourth constraint of M SCP (coloring constraint ( 5)) imply constraints [START_REF] Garey | Computers and Intractability: A Guide to the Theory of N P-Completeness[END_REF][START_REF] Valiant | The complexity of enumeration and reliability problems[END_REF][START_REF] Li | On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem[END_REF], then IP PΣM is a relaxation of M SCP .

Analysis

Note that if we remove the constraint (13) from IP PΣM (or equivalently if we fix m at +∞), we would get a problem equivalent to the one used by Lecat et al. [START_REF] Lecat | New Lower Bound for the Minimum Sum Coloring Problem[END_REF] to find the LBM Σ lower bound:

LBM Σ = ΣM (n, α, s, m = +∞) with α = α(G), if it is known and : s = χ(G) if it is known n α(G) otherwise (16)
Therefore, ΣM is an improvement of LBM Σ, obtained by using the integer m corresponding to the maximum number of IS of size α(G) that is possible to use in a coloring of G graph.

LBM Σ ≤ ΣM ≤ Σ(G) (17)
For this reason, we need to find the smallest possible value of m to have the highest possible value of ΣM . To obtain our value of m, we define a new graph called the maximum independent set graph, noted G = ( Ṽ , Ẽ) as follow.

Definition 1. Let a graph G = (V, E), we call the maximum independent set graph of G, the graph G = ( Ṽ , Ẽ) build as follow :

• each vertex of Ṽ is a maximum independent set2 of G;

• it exists an edge e = (u, v) ∈ Ẽ between two independent sets u ∈ Ṽ and v ∈ Ṽ , if and only if u and v have at least one vertex w ∈ V of G in common (i.e. u ∩ v = ∅); we said that u and v are incompatible because both can not be part of the same coloring of G.

Theorem 2. An optimal sum coloring V * , of a graph G (i.e. an optimal solution of M SCP ) can not have more than α( G) color classes of size α(G) :

|{Vi ∈ V * , |Vi| = α(G)}| ≤ α( G) Proof 2.
Finding the maximum IS of G corresponds to find the maximal number of maximal ISs compatibles in G. In others words, α( G) is the maximum number of IS of size α(G) that are possible to include in a same coloring of G. This is true not only for sum coloring problem but also for all coloring problems.

Therefore, we use in experimental tests, when it is possible to compute it:

m = α( G) (18)
3 Solving IP P

Ordering integer partitions

We defined a relaxation problem, IP PΣM , of M SCP . Our aim is to solve exactly this problem in order to provide a lower bound to M SCP . We define an order between integer partitions corresponding to the objective

function f (a) = n i=1
iai. Given a partition a, we define a set of successor partitions if we move down only one square in the corresponding Young diagram of a by the following rule :

Data: n Fonction successor(a): succ ← ∅ foreach i = 1..n -1 do if ai = 1 ∧ ai+1 < ai then j ← i + 1 while aj ≥ ai -1 do j ← j + 1 b ← change(a, i, j) // we note : b ← a ⊕ (i, j) succ ← succ ∪ {b} return succ
Algorithm 1: Function that return all the successors of the partition a. The change function, noticed ⊕ operator, is defined as follows : Data: n Fonction change(a,i,j):

foreach k = 1..n do b k ← a k bi ← ai -1 bj ← aj + 1 return b Algorithm 2:
Function that return a neighbor partition of a, just two values of b differ from a; we note b ← a ⊕ (i, j) Figure 4 illustrates the successor operator with Young diagram. Algorithm 1 shows that it is possible to move down the last square of each line if :

• the following line has not the same number of squares; it is why the red square of first line of Figure 4 can not move. • the line has not an unique square; it is why the orange square of last line of Figure 4 can not move.

When it is possible to move down a square (case of blue and green squares of Figure 4), the square takes last place of the first possible line. Blue square of Figure 4 can take the place in the just following line. But green square of Figure 4 must go two lines down.

Remark 1. By construction, if a is an admissible solution of IP PΣM , then all of a's succesor interger partitions are also an admissible solution of IP PΣM . In other words, by noting Ω(IP PΣM ) the set of all admissible solutions of IP PΣM : if a ∈ Ω(IP PΣM ), then succesor(a) ⊂ Ω(IP PΣM ). Figure 4: Illustration for the way we find the two successors of a partition a: a1 and a2. From a, we move a square from a line i(= 2 or 3) to the closest line j where ai > aj; j = 4.

We define symmetrically the predecessor function :

Data: n, α, s, m Fonction predecessor(a): pred ← ∅ foreach i = 2..n -1 do if [(i ≤ s ∧ ai > 1) ∨ (i > s ∧ ai > 0)] ∧ [(i ≤ m ∧ ai-1 < α) ∨ (i > m ∧ ai-1 < α -1)] ∧ ai+1 < ai then j ← i -1 while j = 1 ∧ aj ≥ aj-1 do j ← j -1 b ← change(a, i, j) pred ← pred ∪ {b} return pred
Algorithm 3: Function that returns all the predecessors of the partition a. Figure 5 illustrates the predecessor operator with Young diagram. Algorithm 3 shows that it is possible to move up the last square of each line i > 1 if :

• the line just below (i + 1) has not the same number of squares; it is why the red squares of the two first lines of partition a of Figure 5-up-right can not move. • the line just above (i -1) has strictly less than α squares if i -1 ≤ m; it is why the red square of the third line of partition a of Figure 5-up-right can not move. • the line just above (i -1) has strictly less than α -1 squares if i -1 > m; this constraint and the previous one define the hashed area (forbidden area) of Figure 5-up-right. • the square of line s is alone on its line; it is why the red square of last line of partition a of Figure 5-up-right can not move. This mandatory square is noted in bold on Figure 5-up-right.

When it is possible to move a square up (case of blue and green squares of partition b of Figure 5-center), the square takes last place of the first possible line (line 3 and 5 respectively). Theorem 3. If a partition b is a successor of the partition a (respectively b is a predecessor of a), so that b ← a ⊕ (i, j), therefore j > i (resp. i < j) and

f (b) = f (a) + j -i > f (a) (resp. < f (a)) (19)
Proof.

f (b) = n k=1 kb k = k =i; k =j kb k + ibi + jbj = k =i; k =j ka k + i(ai -1) + j(aj + 1) = n k=1 ka k -i + j = f (a) -i + j
If we list the partitions of an integer, we can compare their costs (of sum coloring) using this theorem. We get a comparison relation between partitions which is similar to the comparison relation between motifs used in [START_REF] Lecat | New Lower Bound for the Minimum Sum Coloring Problem[END_REF] (definition 4).

As an example, the Figure 6 presents a graph with n = 9 vertices for which it exists an unique maximum IS of size 6 (α = α(G) = 6 and m = 1). Moreover we take s equals to the chromatic number χ(G) = 3. Figure 7 details all the integer partitions of n = 9 in the form of Young diagram as well as their order. The optimal solution of IP PΣM is the integer partition without valid predecessor.

Resolution of the relaxed problem IP P ΣM

The optimal integer partition of IP PΣM is the integer partition without predecessor.

Without constraint as ≥ 1

We define (IP P0) an intermediate problem corresponding to IP PΣM but without the constraint (13): as ≥ 1.

Let a * 0 the optimal partition of (IP P0); this partition is a function of n, α and m. By definition, a * 0 (n, α, m) satisfies the constraints of (IP P0) and has no valid predecessor among these constraints. To have the best cost (which implies no predecessor), the partition contains as many lines (i.e. color classes) of maximal size (equal to α) as possible. m corresponds to the maximum number of lines of size α, then we take :

m = min n α(G) , #IS(α(G)), α( G)
where #IS(k) is the number of ISs of G with size equals to k a positive integer. α(G), #IS(α(G)) and α( G) can be calculated with the open source code MoMC3 [START_REF] Li | On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem[END_REF]. If it is too time-consuming, we take: m = n α . The remaining integer n -m × α uses then as many independent sets of size α -1 as possible.

Theorem 5. Let be the euclidean division of n -mα by (α -1) :

n -mα = q × (α -1) + r (20)
with q and r < α -1 two positive integers, therefore the optimal partition of (IP P0) is :

a * 0 = ( m α, α, ..., α, q α -1, ..., α -1, r) (21)
and the optimal objective function is equal to : An young diagram of the optimal partition a * 0 is given is Figure 8. The number of lines with maximum lengthy can not be over m.

ΣM0(n, α, m) = fΣM (a * 0 ) = m(m + 1) 2 α + q(2m + q + 1) 2 (α -1) + (m + q + 1)r (22)

With constraint as ≥ 1

If we know that we have to use at least s lines (i.e. colors), we have two possibilities :

• the previous solution already uses s lines, i.e. m + q + 1 ≥ s. Then the optimal solution of (IP P0) is also the optimal solution of IP PΣM , so :

ΣM = ΣM0(n, α, m) = fΣM (a * 0 )
• the previous solution uses less than s lines. Then we start with one vertex in s different sets and we solve (IP P0) with the remaining vertices (n -s) to find the solution. An illustration is given in Figure 10. Theorem 6 gives the cost of the optimal partition. The optimal partition of IP PΣM noted a * is equal to:

a * (n, α, s, m) = a1×s • a * 0 (n -s, α -1, m) (23)
with a1×s = ( s 1, 1, ..., 1) the partition of the number s into ones and with a * 0 (n-s, α-1, m) the optimal partition of (IP P0) with n -s, α -1 and m parameters, therefore:

ΣM = s(s + 1) 2 + ΣM0(n -s, α -1, m) (24)
4 Lower bound for graph coloring

The relaxation used for MSCP can also be applied for GVCP. GVCP is a special case of MSCP for which all colors have the same cost, then let be a possible formulation of GVCP :

(GV CP )    Min. fχ(V) = |{V l | |V l | > 0, ∀l = 1..n}| (25) s.c. Eq. (2 -5) V l ⊂ V ∀l = 1..n
This formulation differs from MSCP just by the objective function, that counts the number of non-empty partitions. Therefore, the relaxation into an integer partition problem becomes :

(IP Pχ)    Min. fχ(a) = |{ai|ai > 0, ∀i = 1..n}| (26) s.c.
Eq. (9 -12) a = (ai) 1≤i≤n ∈ N n Again IP Pχ differs from IP PΣM just by the objective function, that corresponds to the number of lines in Young diagram and because Eq. ( 13) is useless. In this case, the optimal objective function value is equal to :

LBχ = fχ(a * ) = m + q + [r = 0] (27)
with m, q and r given by the Thm.5 and a * the optimal solution of IP Pχ and [ ] is Iverson bracket : [r = 0] = 1 if r = 0 is true and equals 0 otherwise. LBχ is a lower bound of χ(G) and its value depends only of three integers: n, α and m.

Results

Procedure

To compute our lower bound ΣM , we use G the complementary graph of G. We run MoMC solver to find α(G), the size of the maximal clique of G. We also save the list of all the maximal IS of G to compute #is and to build G. Algorithm 4 recall the global procedure to compute ΣM .

Data: G, n α ← α(G) if it is not too time-consuming with MoMC solver, α(G) otherwise. #is ← #is(α) if it is not too time-consuming with MoMC solver, n α
otherwise. Build G, the graph of the maximum IS.

α ← α( G) if it is not too time-consuming with MoMC solver, #is otherwise. m ← min n α , #is, α q ← n-mα α-1 r ← n -mα -q × (α -1) s ← χ(G) the best known lower bound of χ(G) if it is known, n α otherwise. ΣM ← ΣM0(n, α, m) if m + q + 1 ≥ s s(s+1) 2 + ΣM0(n -s, α -1, m) otherwise Algorithm 4: Procedure to compute ΣM .

Empirical Results and Analysis

We tested our procedure on some graph instances of DIMACS and COLOR benchmarks, which are frequently used for performance evaluation of M SCP algorithms [START_REF] Jin | Hybrid evolutionary search for the minimum sum coloring problem of graphs[END_REF]. For several instances, the list of maximum independent set takes too much computational time to be found. There are two possible reasons for this :

• G is too dense and MoMC needs too much time to find a maximum clique.

• the number of maximum cliques is too high and we can't compute their graph.

In our tests, we reuse open source code (MoMC and Cliquer) written in C and we write a script coded in Python 4 . The results were obtained with an Intel Xeon E5 2.50GHz processor -8 cores and 16GB of RAM.

In the Table 1, we show a set of results, focused on graphs where our lower bound could be computed. We compare our lower bound, ΣM , to Σ old (the best lower bound known according to [START_REF] Jin | Algorithms for the minimum sum coloring problem: a review[END_REF], [START_REF] Lecat | New Lower Bound for the Minimum Sum Coloring Problem[END_REF], [START_REF] Wu | Minimum sum coloring for large graphs with extraction and backward expansion search[END_REF]) and LBM Σ (lower bound described in [START_REF] Lecat | New Lower Bound for the Minimum Sum Coloring Problem[END_REF], that we calculate or update for several graphs). The three first columns indicate the graph instance name, its number of vertices and its density. Columns 4 and 5 give the maximum independent set of the graph, α(G) and the time (in second) required to compute it with the MoMC solver. The two next columns show the number of maximum independent set of the graph, #is and the time (in second) required to compute it with the MoMC solver or the Cliquer solver. Columns 8 and 9 indicate, m, the maximum number of compatibles independent sets of the graph and the time (in second) required to compute it with the MoMC solver. If #is is too high (> 5000), then the computation of m is not done because it would take too long. Column 10 gives the chromatic number of the graph χ(G), if it is known and its interval of belonging otherwise. Note that this information comes from other algorithms after a computation-time that may be very long. Next column provides the result of our lower bound, LBχ, computed as in section 4. Last five columns display, Σ(G), the chromatic sum when it is known; Σ old , the best lower bound of Σ(G) known in the literature; LBM Σ, the lower bound presented in [START_REF] Lecat | New Lower Bound for the Minimum Sum Coloring Problem[END_REF]; ΣM0, our lower bound computed without s = χ(G); ΣM , our lower bound computed with s = χ(G). * new optimal solution that we proved ** computation was done with the Cliquer 5 [START_REF] Östergård | A new algorithm for the maximum-weight clique problem[END_REF] solver because for listing all maximum cliques Cliquer is faster than MoMC.

On the 37 graphs of this test set, we improve the result for 18 graphs (light blue in Table 1). For 17 graphs we find the same lower bound as in the literature. For 2 graphs, our lower bound is worse than the best lower bound of the literature. The reason is that for these graphs, the approach used by Moukrim et al. [START_REF] Moukrim | Lower Bounds for the Minimal Sum Coloring Problem[END_REF][START_REF] Moukrim | Upper and Lower Bounds for the Minimum Sum Coloring Problem[END_REF] is totally different of ours, based on the decomposition of the graph into partition of cliques. For 9 graphs, the optimal lower bound was already found with the much simpler LBM Σ lower bound. We have proven the exact value of Σ(G) for 4 graphs (with * in Table 1), and have computed an example of optimal coloring. Our approach is similar to that of Lecat et al. [START_REF] Lecat | New Lower Bound for the Minimum Sum Coloring Problem[END_REF] but we outperformed their results by introducing an additional constraint with the integer m.

Our lower bound of χ(G), LBχ, is equal to the chromatic number for all queen graph instances (13 graphs) and for 4 flat graph instances. Note that for five of those instances (queen5 5, queen7 7, queen11 11, flat300 20 0 and flat1000 50 0 ), we also found the optimal coloring. Indeed, in those cases, the decomposition of the number of vertices is : n = α(G) × m + (α(G) -1) × q + r with q = r = 0, i.e. χ(G) = m. Therefore we know the m compatible independent sets that composed the optimal solution. Moreover, our LBχ is computed in 78 s and 199 s for respectively flat1000 50 0 and flat1000 60 0 graph instances while it takes respectively 3 331s and 29 996s with the most powerful method [START_REF] Held | Maximum-weight stable sets and safe lower bounds for graph coloring[END_REF] to find a lower bound of χ(G).

Conclusion

We presented a new way to find lower bounds for the M SCP and the GV CP . In order to do this, we explained how to relax M SCP into an integer partition problem that can be exactly solved. We can select the constraints we want to keep in this integer partition problem, and we proposed a set of constraints used to define the ΣM lower bound. We carried out experiments and improved the best known lower bound for 18 graphs of standard benchmark DIMACS. We also proved the optimality of 4 of them.

It is also possible to add even more constraints in the integer partition problem. Further researches could use this approach to keep improving the lower bound.

Figure 1 :

 1 Figure 1: Example of graph for MSCP from Jin and Hao [4]. The left coloring uses 3 colors (integers 1, 2 and 3).It is an optimal solution of GVCP and the chromatic number χ(G) = 3. Moreover, its sum coloring cost is equal to 18. The right coloring uses one more color (integers 1, 2, 3 and 4) but its sum coloring cost is equal to 15, which is the chromatic sum of G: Σ(G) = 15.

Figure 2 :

 2 Figure 2: Example of Young diagram for the partition of integer 12 into a sum of four integers : 4, 4, 3 and 1 (12 = 4 + 4 + 3 + 1). Each line corresponds to one positive integer of the partition. Integers are ranked in descending order.

Figure 3 :

 3 Figure 3: Young diagrams of two colorings of the same graph as in Figure 1. Each square represents a vertex. Squares on the same line share the same color. The objective function value of M SCP is calculated by counting the number of squares for each line:

Remark 2 .

 2 If a is an admissible solution of IP PΣM without succesor i.e. successor(a) = ∅, then it means that a is the column partition a = (1, ..., 1 n ).

Figure 5 :Remark 3 .

 53 Figure 5: Illustration of the way we find a predecessor of a partition. The partition a (up-right figure) has no predecessor because the hashed area is the forbidden area and the bold square (last line) is mandatory (a square must be place on it). The partition b has two possible predecessors, b1 and b2, by moving blue square or respectively green square to line 3 or respectively line 5.

Lemme 1 .

 1 For all a and b ∈ Ω(IP PΣM ), it exists a set of k > 1 integer partitions c i ∈ Ω(IP PΣM ), with i = 1...k so that c1 = a, c k = b and c i+1 ∈ predecessor(c i ) or c i+1 ∈ successor(c i ).

Figure 6 :Theorem 4 .

 64 Figure 6: Graph (left figure) with n = 9 vertices with α = α(G) = 6 and m = 1 (it exists an unique maximum IS of size 6) and we take s = χ(G) = 3. Then, the constraints on the Young diagram (right figure)imply that only one line can have 6 squares, the others has at most 5 square (i.e. no squares in the hatched area) and it must have at least one square on the third line (i.e. red square is mandatory).

Figure 7 :

 7 Figure 7: Young Diagrams of all possible integer partitions succeeding a graph G. Each arrow indicates a successor of a partition and the number indicates the additional cost function (of sum coloring) to pass from a partition to the other.

Figure 8 :

 8 Figure 8: Young diagram of the optimal partition a * 0 of (IP P0).

Figure 9

 9 Figure 9 gives an example of optimal partition with n = 16, α = α(G) = 4 and m = 2. Notice that in the

Figure 9 :

 9 Figure 9: Illustration of how to find the best partition given n, α = α(G) and m. The length of a line can not be over α(G). The number of lines with maximum lengthy can not be over m.

Figure 10 :Theorem 6 .

 106 Figure 10: Illustration of how to find the best partition with n = 16, α = 4, m = 2 and s = 7. We add two partitions: the first one is a column of s squares; the second one is the optimal partition of one (IP P0) problem with n = n -s squares, α = α -1 and m = m.

Table 1 :

 1 Results of weak optimality tests on some graphs of DIMACS and COLOR benchmarks.

	Instances	n	d	α(G) time	#is	time	m	time	χ(G)	LBχ	Σ(G)	Σ old	LBM Σ ΣM0	ΣM
	myciel3	11 0.36	5	< 0.1	2	< 0.1	1	0	4	3	?	20	20	19	20
	myciel4	23 0.28	11	< 0.1	2	< 0.1	1	0	5	3	?	41	41	37	41
	myciel5	47 0.22	23	< 0.1	1	< 0.1	1	0	6	3	?	80	81	73	81
	myciel6	95 0.17	47	< 0.1	1	< 0.1	1	0	7	3	?	158	158	145	158
	myciel7	191 0.13	95	< 0.1	1	0.1	1	0	8	3	?	308	308	289	308
	queen5 5	25 0.53	5	< 0.1	10	< 0.1	5	< 0.1	5	5	75	75	75	75	75
	queen6 6	36 0.46	6	< 0.1	4	< 0.1	4	< 0.1	7	7	?	126	127	129	129
	queen7 7	49 0.40	7	< 0.1	40	< 0.1	7	< 0.1	7	7	196	196	196	196	196
	queen8 8	64 0.36	8	< 0.1	92	< 0.1	6	< 0.1	9	9	291*	288	289	291	291
	queen8 12	96 0.30	8	< 0.1	195 271	0.3	#is	×	12	12	?	624	624	624	624
	queen9 9	81 0.33	9	< 0.1	352	< 0.1	7	< 0.1	10	10	?	405	406	408	408
	queen10 10	100 0.30	10	< 0.1	724	0.2	8	0.8	11	11	553*	550	551	553	553
	queen11 11	121 0.27	11	< 0.1	2 680	0.9	11	207	11	11	726	726	726	726	726
	queen12.12	144 0.25	12	< 0.1	14 200	6** #is	×	12	12	936	936	936	936	936
	queen13.13	169 0.23	13	< 0.1	73 712	0.5** #is	×	13	13	1 183	1 183	1 183	1 183	1 183
	queen14.14	196 0.22	14	< 0.1	365 596	3** #is	×	14	14	1 470	1 470	1 470	1 470	1 470
	queen15.15	225 0.21	15	< 0.1 2 279 184 17** #is	×	15	15	1 800	1 800	1 800	1 800	1 800
	queen16.16	256 0.19	16	< 0.1 14 772 512 113** #is	×	16	16	?	2 176	2 176	2 176	2 176
	2-Insertions 3 37 0.11	18	< 0.1	1	< 0.1	1	0	4	3	?	55	59	58	59
	3-Insertions 3 56 0.07	27	< 0.1	11	< 0.1	1	0	4	3	?	84	88	88	89
	DSJC125.1	125 0.09	34	< 0.1	747	< 0.1	1	0	5	4	?	297	297	299	300
	DSJC125.5	125 0.50	10	< 0.1	2	< 0.1	1	0	17	14	?	851	855	918	924
	DSJC125.9	125 0.90	4	< 0.1	9	< 0.1	5	< 0.1	44	40	?	2 108	2 124	2 475	2 487
	DSJC250.5	250 0.50	12	< 0.1	2	< 0.1	2	< 0.1 〚26, 28〛	23	?	2 745	2 745	2 924	2 930
	DSJC250.9	250 0.90	5	< 0.1	3	< 0.1	2	< 0.1	72	62	?	6 651	6 678	7 815	7 882
	DSJC500.5	500 0.50	13	2	51	3	9	< 0.1 〚43, 47〛	41	?	9 867	9 877	10 336 10 339
	DSJC500.9	500 0.90	5	< 0.1	23	< 0.1 15 < 0.1 〚123, 126〛 122	?	25 581 25 581 29 766 29 768
	DSJC1000.5 1000 0.50	15	159	12	290	6	< 0.1 〚73, 82〛	71	?	33 835 33 856 35 805 35 808
	DSJC1000.9 1000 0.90	6	0.1	3	0.1	3	< 0.1 〚216, 222〛 200	?	85 235 85 294 99 906 100 078
	DSJR500.1c	500 0.97	13	< 0.1	4	< 0.1	2	< 0.1	85	42	?	15 398 11 040 10 587	11 619
	DSJR500.5	500 0.47	7	0.3	18	0.8	2	< 0.1	122	83	?	23 609 19 599 20 919	21 832
	flat300 20 0	300 0.48	15	< 0.1	20	< 0.1 20 < 0.1	20	20	3 150	3 150	3 150	3 150	3 150
	flat300 26 0	300 0.48	12	< 0.1	31	1	14 < 0.1	26	26	3 966*	3 901	3 901	3 966	3 966
	flat300 28 0	300 0.48	12	< 0.1	45	1	6	< 0.1	28	27	?	3 906	3 906	4 098	4 099
	flat1000 50 0 1000 0.49	20	36	50	78	50 < 0.1	50	50	25 500 25 500 25 500 25 500 25 500
	flat1000 60 0 1000 0.49	17	89	42	199	40 < 0.1	60	60 30 100* 29 914 29 914 30 100 30 100
	flat1000 76 0 1000 0.49	15	184	21	394	8	< 0.1	76	71	?	33 880 33 880	35678	35 693

Notice that the maximum IS of a graph G is the maximum clique of G.

independent set of size α(G)

code available on: https://home.mis.u-picardie.fr/∼cli/EnglishPage.html

code available on: github.com/gondran/LowBoundSumColoring


Thibaut Barbier¹
email: t.barbier@optimum-tracker.com

Philippe Blanc²

Yves-Marie Saint

SOFTWARE CORRECTION OF ANGULAR MISALIGNMENTS OF TILTED REFERENCE SOLAR CELLS USING CLEAR-SKY SATELLITE OPEN DATA

Keywords: in-situ measurements, angular misalignment, satellite data

In-situ measurements for photovoltaic systems are very sensitive to angular misalignments. It can lead to errors in many steps of a photovoltaic (PV) project. In this paper, we propose a simple and robust method to estimate and correct a posteriori the angular misalignment of tilted reference solar cells or pyranometers. The method uses output of the clear-sky irradiance model McClear, a free Copernicus Atmospheric Monitoring Service. We applied the method in 6-month data composed of 7 different tilted reference solar cells. We find that angular misalignment estimation found in the case study are meaningful. Finally, we showed the angular correction found improves satellite-based estimation of GTI for the 6 following months of data for clear sky days, for both RMSE and bias indicators.

INTRODUCTION AND CONTEXT

In 2018, world photovoltaic (PV) installed capacity crossed the 500 GWp mark [START_REF]Snapshot of the Global PV Markets[END_REF]. The growth is exponential and is expected to continue in the following years [START_REF]Snapshot of the Global PV Markets[END_REF].

Due to this high growth, the market is becoming more competitive, and PV stakeholders are improving more and more the resource assessment, PV production characterization and forecast. All of this relies on accurate solar irradiance data, using in-situ measurements with thermopile pyranometers, photodiode pyranometers, and photovoltaic reference cells [START_REF] Driesse | Investigation of pyranometer and photodiode calibrations under different conditions[END_REF].

In-situ measurements for photovoltaic systems are very sensitive to angular misalignments. For example, they increase errors in solar resource estimation or nowcasting [START_REF] Killinger | Projection of power generation between differently-oriented PV systems[END_REF]. They also reduce the accuracy of cloud tracking algorithms (e.g. in [START_REF] Arliaud | Procédé de pilotage de l'orientation d'un suiveur solaire basé sur des modèles cartographiques[END_REF]). Angular misalignment can occur e.g. during the installation or the operation, notably due to temperature gradients, wind efforts, birds, etc.

In parallel to in-situ measurements, satellite-derived irradiance databases can provide complementary and easily available data (e.g. [5]). Satellite data provide a stable measurement that can be compared with in-situ measurements to detect and correct angular misalignments, to avoid the important errors described previously.

In this paper, we propose a method for estimating the angular misalignment of tilted reference solar cells or pyranometers using output of the clear-sky irradiance model McClear, a free Copernicus Atmospheric Monitoring Service.

DESCRIPTION OF THE METHOD

The proposed method needs preliminary in-situ measurements of global tilted irradiance (GTI) of reference solar cell or pyranometer. The goal is to estimate the angular misalignment of the sensor and eventually correct it. For that purpose, we compare the measurements with output of the clear-sky irradiance model McClear, a free Copernicus Atmospheric Monitoring Service [6]. An illustration of the method is given in Figure 1. The comparison of measurements and satellite data is done using Perez luminance transposition model [START_REF] Perez | All-weather model for sky luminance distribution-preliminary configuration and validation[END_REF] In order to test the method, one-year data (2017) from Opti-SkyControl© sensors developed by Optimum Tracker company are used. Data are recorded at 1min time step for a site located in South Est of France. Opti-SkyControl© is derived from an Optimum Tracker's patent [START_REF] Arliaud | Procédé de pilotage de l'orientation d'un suiveur solaire basé sur des modèles cartographiques[END_REF] and is designed for North-South 1 axis solar trackers, in order to estimate the PV production at any angle. Opti-SkyControl© is composed by 7 reference cells with different tilts: -35°, -20° and -10° facing East, 0° horizontal cell and 10°, 20° and 35° facing West. Reference cells were calibrated by meteocontrol before the commissioning. Opti-SkyControl© also includes a pyranometer and a hemispheric camera that are not used in this case study. Solar azimuth and elevation are computed at every time step using pvlib python library [START_REF] Holmgren | pvlib python: a python package for modeling solar energy systems[END_REF]. Ground albedo is set to a standard value of 0.15.

Results and discussion

Perez transposition model together with IAM model on the direct irradiance component part is applied on satellite data for the first 6 months of data (from January to June 2017). Different tilt and azimuth angles are tested for each solar cell, and the correct angle is chosen by minimizing the root main square error between satellite irradiance projection and in situ measurements. Resulting angles are put in Table I. We can notice the corrected angles in azimuth found to be added are all between 4.62° and 5.53° to add. It means the Opti-SkyControl© must be shifted of around 5° to in the North direction when facing the East direction. Tilt angle corrections have a maximum deviation of 2.85°for 0° tilted sensor. Deviation found is between 1.81° and 0.32° for other sensors. Regarding these results, the mast holding the Opti-SkyControl© must face a small deviation from the horizontal.

In order to test the interest of the method, the simulated GTI is computed from the satellite derived irradiance for a priori azimuth and tilt angles, and for the new corrected angles. The simulation is done in the 6 next months of data (from July to December 2017) to ensure a cross-validation and is compared to in-situ measurements. Results are displayed in Figure 4 and Figure 5. When analysing results in Table II, we can see that the best RMSE and bias improvments are obtained for -35° and -20° reference cells. Then comes -10 and 0° reference cells. These results are coherent with the value of the angle corrected in Table I : these 4 sensors have higher tilt angle correction than the 3 others. We clearly see the improvment of the 6 months for the 7 sensors, from 11.9W/m² to 0.2W/m² for the RMSE improvement, from 14.3W/m² to 2.21W/m² for bias improvement. Figure 5 illustrates temporally the improvement obtained in the satellite-derived GTI before and after correction in a particular day. We observed that angular misalignment estimation found in the case study are meaningful. Then, we showed angular corrections improve satellite-based estimation of GTI for the 6 following months for clear sky days, for both RMSE and bias indicators. A next possible step is to make a dynamic correction to detect significant misalignment variations. Also, the angles found by the method can be compared with on-site precise azimuth and tilt measurements of the sensors.

Figure 1 :

 1 Figure 1: Illustration of the different steps of the software correction method for angle misalignments

Figure 2 :

 2 Figure 2: Opti-SkyControl© Sensors developed by Optimum Tracker company For the comparison, CAMS McClear data are downloaded for the corresponding site with clear sky global horizontal irradiance (GHI) and clear sky diffuse horizontal irradiance (DHI). Cloud-free days are selected manually using in-situ measurements and used for the misalignment correction (9 full clear sky days in the first six months, and 8 full clear sky days in the last 6 months in the dataset).

Figure 3 :

 3 Figure 3: Example of clear sky day irradiance plot showing both in-situ pyranometer measurement and irradiance from clear sky McClear model.

Figure 4 :

 4 Figure 4: All sensors measurements in the second 6months 2017 period in clear sky days vs GTI from McClear model, with a priori tilt and azimuth angles.

Figure 5 :

 5 Figure 5: All sensors measurements in the 6 lastmonths 2017 period in clear sky days vs GTI from McClear model, with corrected tilt and azimuth angles. Correction was done in the first 6-month 2017 period. The results show significant reduction of the RMSE (-5.1W/m²) and Bias (-7.6W/m²) indicators for all sensors included. Table II details the results for each reference cell.

Figure 6 :

 6 Figure 6: Comparison with -35° tilted reference cell and satellite-derived GTI before and after correction 4 CONCLUSION AND PERSPECTIVES In this paper, we proposed a simple and robust method to estimate and correct a posteriori the angular misalignment of tilted reference solar cells or pyranometers using output of the clear-sky irradiance model McClear, a free Copernicus Atmospheric Monitoring Service.We observed that angular misalignment estimation found in the case study are meaningful. Then, we showed angular corrections improve satellite-based estimation of GTI for the 6 following months for clear sky days, for both RMSE and bias indicators. A next possible step is to make a dynamic correction to detect significant misalignment variations. Also, the angles found by the method can be compared with on-site precise azimuth and tilt measurements of the sensors.

Table I :

 I Value of the correction of the different angles

	Reference cell	Correction angle	Correction angle
	tilt angle (°)	to add in azimut	to add in tilt (°)
		(°)
	-35	4,88	1,81
	-20	5,02	1,34
	-10	4,96	1,31
	0	5,12	2,85
	10	5,32	0,32
	20	5,53	0,45
	35	4,62	1,18

Table II :

 II RMSE and bias values and improvement in the comparison of the 6 last-months 2017 period dataset

	Reference	RMSE	RMSE after	RMSE
	cell tilt (°)	before	correction	improvment
		correction	(W/m²)	(W/m²)
		(W/m²)
	-35	32,50	20,90	11,60
	-20	29,50	17,60	11,90
	-10	39,5	33,70	5,80
	0	31,50	27,60	3,90
	10	23,60	21,60	2,00
	20	21,90	21,50	0,40
	35	27,90	27,70	0,20
	Reference	Bias before	Bias after	Bias
	cell tilt (°)	correction	correction	improvement
		(W/m²)	(W/m²)	(W/m²)
	-35	-11,5	2,38	13,88
	-20	-17,5	-3,2	14,3
	-10	-28,1	-20,7	7,4
	0	-17,9	-11,7	6,2
	10	-15	-9,32	5,68
	20	-8,28	-4,96	3,32
	35	-10,3	-8,09	2,21


Thibaut Barbier
email: t.barbier@optimum-tracker.com

Philippe Blanc

Yves-Marie Saint-Drenan

Software correction of angular misalignments of tilted reference solar cells using clear-sky satellite open data

Description of the method


domain: info spi.gciv stat

text:
Ahmed Junaid

Lan Khan

Eddie Wang

Ahmedraza Jacobs

Sabyasachee Talebian

Charles A Mishra

Mihalis Santo

Carmen Golias

Astorne-Figari

Smart Cities Connected and Autonomous Vehicles Readiness Index

Keywords: Connected and Autonomous Vehicles (CAVs), Smart Cities, Readiness Index

Every major car manufacturer and leading technology company today is pursuing the development of Connected and Autonomous Vehicles (CAVs). However, given cities will be most affected by CAVs, there is an urgent need to assess whether our cities are prepared and will respond well to the advancement in CAV technology. This paper proposes the first readiness index to measure the extent to which current cities are ready for CAVs. We consider three key elements in computing a CAV readiness score: a city's policies and regulations, its physical infrastructure, and its cyber infrastructure. We identify 16 major factors related to the key elements contributing to a city's readiness, and compute the readiness index as a weighted average of these factors. Moreover, we collected survey responses regarding the importance of each factor from 13 of the most populous US cities. We also selected a metric for quantifying each factor, and collected the corresponding data from our survey and existing studies. We then leverage decision trees as a machine learning model to predict 52 major US cities' readiness for CAVs. While it is difficult to draw general conclusions on our cities' readiness due to limited data availability, our preliminary study does suggest that there is a big gap between our industry and public's interest in CAVs and the policy and infrastructure support provided by our cities. Most importantly, we believe that the proposed readiness index provides practical guidelines for policy makers and planners to improve their cities' policies and infrastructure to facilitate CAVs.

INTRODUCTION

The increase in Connected and Autonomous Vehicles (CAVs) development by car manufacturers and technology companies can potentially have a significant impact on our cities. It will not only affect the existing urban transportation system but also impact citizens' mobility trends and lifestyle. Although the adoption of CAVs by citizens depends on their preferences, market prices, and other factors [START_REF] Talebian | Predicting the adoption of connected autonomous vehicles: A new approach based on the theory of diffusion of innovations[END_REF][START_REF] Simpson | Disaggregated prediction of adoption rate of autonomous trucks by freight organizations[END_REF], we believe that cities need to proactively plan for CAV deployment by taking the necessary steps to improve their policies and infrastructure in order to facilitate CAVs. However, there are currently no concrete methodologies to measure the extent to which our cities are ready for CAVs.

This paper presents a "CAV readiness index" to measure a city's readiness for CAV deployment. We first identified the following three key elements in facilitating CAV deployment.

(1) Policy and Regulations: a city can adopt policies and regulations that make it easier for citizens and businesses to use CAVs. For example, a city may invest in projects related to CAVs or encourage such projects by providing tax incentives. It may also establish traffic rules that privilege CAVs in certain parts of the city. Establishing and enforcing such policies and regulations typically requires a dedicated CAV department within the transportation department. (2) Physical Infrastructure: safe operations of CAVs depend on the availability and maintenance of adequate physical infrastructure such as high quality road markings and signage, high density of Electric Vehicle (EV) charging stations, as well as other CAV compatible infrastructure. (3) Cyber infrastructure: CAVs utilize a variety of data for decision making in their navigation including data from their own sensors, data obtained from other vehicles, and data from the Internet. Therefore, their operations depend on the Internet infrastructure, Intelligent Transportation Systems (ITS), road-side units (RSUs), data centers, and other cyber infrastructure. The availability and security of such cyber infrastructure will impact the safety of the CAVs.

We further refined the above three elements into 16 factors, and computed the readiness index as the weighted average of all factors, where the weights are derived from the responses to a survey sent to experts in major cities. In particular, we collected feedback from the Metro Planning Organizations (MPOs) and Chief Information Officers (CIOs) of 13 major cities. We then predicted the readiness of 52 US cities using various machine learning algorithms and selected decision trees for our final prediction based on its performance. We trained our models using real data collected from the 13 US cities and data from other sources.

The contributions of this research are summarized as follows:

• We identify three key elements divided into 16 factors necessary to measure a city's readiness towards CAVs. • We define a numerical CAV readiness index as a weighted average of all 16 factors. • We determine the weighting factors from the analysis of 13 received responses to a survey sent to planning and technology experts such as MPO officials and CIOs of 52 cities. • We leverage decisions trees as a machine learning model to predict the overall readiness, as well as the policy, physical and cyber infrastructure readiness of all 52 US cities.

The organization of the paper is as follows. Section 2 presents the factors contributing to CAV readiness and the methodology for computing the proposed readiness index. Section 3 presents our prediction method and results regarding the readiness of 52 US cities. Finally, Section 4 concludes the paper.

CAV READINESS INDEX

Readiness Indices have been measured before in different domains, such as in health sciences for organ donation [START_REF] Rice | A confirmatory analysis of the organ donation readiness index: measuring the potential for organ donations among african americans[END_REF], technology adoption [START_REF] Parasuraman | An updated and streamlined technology readiness index: Tri 2.0[END_REF], governance [START_REF] Ayanso | E-government readiness index: A methodology and analysis[END_REF][START_REF]Global e-government readiness report: Toward access for opportunity[END_REF], hospitality [START_REF] Victorino | Exploring the use of the abbreviated technology readiness index for hotel customer segmentation[END_REF], education [START_REF] Semih Summak | Technology readiness of primary school teachers: A case study in turkey[END_REF] and smart urbanization [START_REF] Anwer | Towards an index of city readiness for cycling[END_REF]. A recent survey published an autonomous vehicle readiness ranking different countries [START_REF] Kpmg | Autonomous vehicles readiness index[END_REF]. Different from their work, we predict the readiness of cities instead of countries towards Connected and Autonomous Vehicles (CAVs). Their work concentrates on the policies and regulations defined by a country's government that can facilitate CAVs in the country. Similarly, INRIX [START_REF]Highly autonomous vehicle city evaluation[END_REF] performed a study to rank top US cities for Autonomous Vehicles based on citizens' travel and mobility patterns. They identified issues in current policies and looked into the societal impacts of adopting Autonomous Vehicles. In contrast to the INRIX study, our work identified factors related to not only a city's policies but also a city's physical and cyber infrastructure as these are essential for the safe and efficient operations of CAVs.

We collected real data from the representatives of different cities in the United States regarding the importance of each factor contributing to CAV readiness and then leverage the machine learning algorithm, decision trees to predict the readiness of each city with respect to the CAV deployment.

We sent questionnaires to CIOs and MPO officials from each city asking them to respond on a scale of 1 -5 regarding their opinion on the impact of each element, where a response of 5 corresponds to high impact and 1 corresponds to low impact from the city administration officials. For each element, we computed the average score from the responses of all participants, normalized between 0-1 to find its respective weight, while the sum of weights in each category sums to unity.

Figure1 shows the three major categories composing our readiness index, with weights shown in parentheses. We computed these weights by taking the average of the weights suggested individually by each of the experts who completed our questionnaire. Using this procedure, we obtained a weight of 0.31 for policies and regulations, 0.33 for physical infrastructure and 0.36 for cyber infrastructure. Each of these categories is composed by a number of elements, as Figure 1 shows. Each element of a category receives a weight that was calculated using a similar procedure. All elements are summarized in Table 1 with the scoring method described in the last column where each will be explained in the rest of this section.

We believe it would be interesting to emphasize the individual importance of each element irrespective of their relative weight, therefore, in the remainder of this section, we will also mention the individual importance score provided by experts for each element.

In our survey, we requested CIOs and MPO officials from each city to respond on a scale of 1 -5 regarding their opinion on the importance of each element, where a response of 5 corresponds to strong agreement (important) and 1 corresponds to strong disagreement (not important) from the city officials. In the remainder of this section, we will mention the individual score provided by experts for each factor.

In this work, we assume that the MPO officials and CIOs of the most populous cities in the United States are well qualified to assess the importance of different factors we considered in composing the CAV readiness index. Moreover, they are also able to provide concrete data regarding their cities' policies and infrastructure. Therefore, we sent our survey only to these experts. For our future study, we will consider collecting opinions from other segments of the society, e.g., the general public or technologists, and compare them with those from the MPOs and CIOs.

CAV Readiness: Policies and Regulations

A city's readiness towards CAVs is reflected by the dedication of its administration to put forward reforms and policies that can facilitate CAVs' utilization by its citizen. We asked the question of whether "New policies and legislation are needed by the city administration/policy makers to make today's cities ready for CAVs' where on a scale of 1-5, the average response yielded an importance score of 4.16, This is general agreement in the need to revise current policies and legislation to accommodate CAVs.

CAV department.

An important factor required in order to define rules and regulations regarding CAVs is for a city to establish a dedicated CAV department within its transportation department. This allows the administration to regulate and modify policies to accommodate CAVs in an efficient manner. For instance, legalizing CAVs to use certain lanes can be part of the CAV department's responsibility. Similarly, regulating licenses and evaluating a CAV's capability to operate on city roads can be efficiently achieved in the existence of such a dedicated department. New Zealand, UK and UAE have already established such departments in their cities [START_REF] Kpmg | Autonomous vehicles readiness index[END_REF]. We asked the "Impact of having dedicated team or staff members within the transport department for CAVs" from city administration officials and the average impact score is 3.75.

CAV investments. The city administration's investment in

CAV related infrastructure is a vital factor to decide the extent the city is ready to facilitate the use of CAVs. The technological constraints today do not allow CAVs to fully operate on current roads and therefore can be driven only in specialized infrastructure with assistance. This requires dedicated testing zones for such vehicles where full external support can be provided for their operation. A simple measure would be to count the amount of money the city administration invested for CAV testing and related pilots/projects. As an example of such investment, the Dutch government recently invested 90 million euros to enable more than 1, 000 traffic lights across the country to communicate with vehicles [START_REF] Kpmg | Autonomous vehicles readiness index[END_REF].

We asked from the officials from different cities, "How much investments by the city administration in CAV related projects and research impacts its readiness for CAVs?". We obtained an average importance score of 3.

CAV privileges.

This factor measures the rules and regulations defined by the city that prioritize CAVs' usage. One such rule can be allowing CAVs to use High Occupancy Vehicle (HOV) lanes even in the presence of a single person in the vehicle. Similarly, roads in city centers or downtown areas are usually congested and allowing only CAVs to access these roads motivate citizens towards the use of CAVs. In addition to such rules, the city administration can privilege CAVs' to park in dedicated spaces even in congested areas or providing them with tolling privileges compared to humanoperated vehicles. The city administration can also define rules to prioritize CAVs to use safety harbors on highways while ensuring any misuse of safety harbors is prevented. In response to our question on the "Impact of having traffic rules that prioritize CAVs (i.e. in HOV lanes, parking spaces, etc)", the city administrators responded with an average impact score of 3.33.

CAV Readiness: Physical Infrastructure

The current road infrastructure should be prepared and adapted to the CAV specific needs and therefore, physical infrastructure readiness readiness is an important criterion to consider towards a city's readiness. We asked different city administration officials whether "Improved physical infrastructure (road quality, signage, parking tolling facilitates etc) makes the cities ready for CAVs. The average importance score of 4.1 clearly indicates the perceived importance of a city's physical infrastructure. This section below specifies key factors contributing to the physical Infrastructure readiness.

2.2.1 Infrastructure quality. One of the key factors is the quality of the city's physical infrastructure. Unlike human drivers, the computing and processing capabilities on-board a CAV would require more clear details of the city's physical infrastructure to accurately detect road markings and signage for its driving decisions. Therefore, the city should regularly maintain high-quality road markings and signage by ensuring they do not wear off easily and are clearly detectable. We asked the "Impact of Infrastructure quality (roads, bridges, clear road marking and signage etc) on CAVs" to which a score of 4 suggests a need of maintaining a high quality road infrastructure in order to accommodate CAVs.

One way of quantifying this measure is to evaluate how frequent the city administration inspects the quality of its roads, bridges, road markings, signage and how often it schedules repairs and repainting. Moreover, the number of smart cones and beacons over the total road mileage in the city can also be considered towards the physical infrastructure quality. We consider the existence of A city might have a large number of EV stations compared to other cities but the number might not be sufficient for its population. Therefore, this factor should be normalized with respect to the city's population. The publicly available data on the number of EV charging stations normalized with respect to population for each city is collected from [START_REF] Chargehub | Ev charging stations map[END_REF] . We asked experts, "How much having large number of electric vehicles charging stations in the city impact its readiness for CAVs", in response to which an impact score of 3.52 was provided.

CAV compatibility.

The city should design new CAV compatible parking facilities and road lanes. Additionally, the existence of dedicated CAV-only pick-up and drop-off areas contribute to the infrastructure readiness as CAVs operate differently compared to human drivers and having dedicated areas will ease their usage. It is also important to find out whether the city has developed any CAVonly pick-up/drop-off areas in crowded areas. In our questionnaire, we inquired regarding the "Impact of having new CAV compatible lanes, parking and tolling facilities in the city" to which an average impact score of 3.57 was provided by city administration officials.

CAV Readiness: Cyber Infrastructure

The technological evolution of today's cyber infrastructure plays a key role in facilitating CAVs' usage. In this section, we identified three key cyber infrastructure elements that can be considered towards a city's CAV readiness index. In response to our comment "Improved cyber infrastructure (Mobile network coverage, ITS infrastructure, etc ) makes the cities ready for CAVs", the city administration provided an average importance score of 4.3, thus indicating that cities should prioritize making improvements to their cyber infrastructure to help facilitate CAVs on their roads.

Network availability.

An important aspect of the cyber infrastructure readiness is seamless Internet availability in order to efficiently move CAV related data. To this extent, we consider the following three types of network availability in the city. An average impact score of 3.65 was obtained regarding the "Impact of having Road Side Units (RSUs) for short range communication between vehicles and infrastructure". • Fiber network availability: The availability of a city-wide optical fiber network is also important for CAVs' connectivity.

A city can connect all the RSUs using such a network where the information from the CAVs can be efficiently transmitted through these RSUs. The length of fiber cable per population can be considered to measure this element, however, due to the unavailability of such data, we considered the availability of fiber Internet in each of the considered cities as a binary variable. The "Impact of having a city-wide optical fiber network" was scored 4.05.

Data analytics.

We live in the era of Big-data and the constantly generated and consumed data on urban streets plays a vital role in facilitating CAVs. We asked different city administration officials and they agree with us by providing an importance score of 4.2 on a scale of 1 -5 that "Efficient Intelligent Transportation System (ITS) measures should be available" for data analytics in the urban environment.

• Pedestrian/obstacle detection technology for infrastructure: Roadside cameras alone are a great source of urban Big-data and can be leveraged to assist CAVs' operation. Therefore, the amount of roadside cameras or other infrastructure equipped with state-of-the-art pedestrian detection technology is an important factor that facilitates CAVs' driving and maneuvering. This requires intelligent software and machine learning algorithms at the infrastructure that can process data from cameras, extract useful information, and communicate it to the CAVs in real time. A large number of cameras equipped with such intelligent pedestrian detection techniques can further enhance pedestrian detection capabilities by using I2V communication thereby informing CAVs regarding any hazard in a timely manner. In our survey, we collected the pedestrian detection technology availability information as a binary variable and asked regarding the "Impact of pedestrian detection technology availability in the Intelligent Transportation System (ITS) infrastructure" and an average impact score of 4.15 was provided. • Local data center availability: Beside roadside cameras, CAVs will also generate and consume lots of data. To efficiently process and analyze such large amount of Big data, there should be a local data center within the city. Such a data center can also be served as a control center for all ITS related operations and will assist CAVs' while driving.

We collected data on a data center availability as a binary variable in each of the considered cities and asked regarding, "The impact of data center availability within the city to store, process and analyze the data collected from urban streets". An average impact score of 4.1 was provided by experts. • 3D maps of the road network: One aspect towards CAVs' readiness is the availability of high resolution and 3D maps of the city. CAVs can store such maps locally with no Internet requirements in bad weather where there is low Internet connectivity. We collected the 3D maps availability information as a binary variable for each city and asked, "How much having city-wide 3D maps are important for its readiness towards CAVs?", An average impact score of 3.4 was provided.

• ITS availability in the city: There already exists a satisfactory ITS system in some cities. However, the availability of such resources should be enhanced such as the installation of sensor-equipped cones and beacons at work sites along with having roadside information communication devices where needed to be able to interact with CAVs. We collected the availability of sensor-equipped cones and beacons as a binary variable for each city and asked experts: "How much availability of sensor-equipped cones, beacons and roadside information communication devices impacts a city's readiness" and in response, an impact score of 3.6 was provided.

2.3.3 Cyber security. One important aspect of CAVs' operation is securing the ITS infrastructure and communication against either physical or cyber attacks. The city should also be able to handle a disaster situation as a result of hacking or jamming its cyber infrastructure in order to ensure the safety of its citizens. In response to "Measures are needed for cities to cope with CAV related cyber security issues (cater threats such as hacking/jamming of the CAV communication, etc)", an impact score of 4.2 was provided.

• Infrastructure security: The security of a city's ITS infrastructure against any possible cyber attacks (i.e. hacking of the traffic lights, etc) is a factor in CAV readiness.We collected data on the availability of such measures as a binary variable and inquired regarding the "Importance of securing the available ITS infrastructure (cameras, RSU etc) from possible physical and cyber attacks". An impact score of 4.9 was provided by city administration officials. • Communication security: CAVs' greatly rely on communications with other nearby vehicles and RSUs and jamming or hacking V2X or I2V communication can be deadly. Therefore, we consider a binary variable as a measure for securing the short-range communication between CAVs and infrastructure towards the readiness index of the city. The "Importance of securing the short range communication between CAVs and infrastructure against hacking and jamming" had an impact score of 4.85, thus requires high attention from policy makers. • Disaster recovery: The city administration is usually prepared for natural disasters. However, disasters and security threats caused by CAVs have not been discovered yet . The readiness for CAVs should consider how well the city is prepared when anything goes wrong and its capability to respond to potential CAV related disaster and security threat. Thus, we consider the existence of such a measure as a binary variable that contributes towards a city's CAV readiness. For the question on the "Importance of availability of disaster response unit for recovery after disaster/attack related to CAVs", the average impact score of 4.9 was provided.

CAV READY CITIES

We predicted the readiness of 52 US cities based on the collected data regarding the proposed 16 factors. The Chief Information Officers (CIOs) and (Metropolitan Planning Organization (MPO) officials of the 52 cities were contacted and 13 provided the information required to compute the readiness index. The readiness of the remaining cities is predicted using Decision tree model. We employ the leave-one-out as our cross-validation method where, for validation, we use the readiness score computed based on the responses from the officials of each of the compared cities.

Predicting Readiness

We use Decision trees to predict the policy, physical and cyber infrastructure readiness of the 52 cities. The features we used to correlate similar cities are (i) population count in 2017 and the (ii) growth in population between 2010 and 2017. Further, we consider (iii) the city's Gross Domestic Product (GDP) in 2017 and its (iv) GDP growth between 2012 and 2017 along its (v) GDP per capita in 2017 as a feature to classify similar cities in order to predict their readiness.

We cross-validated the predicted values from the decision tree model by comparing it with the readiness computed from the responses collected for the 13 cities This makes 25% of training data with ground truth information for the decision tree to predict the readiness values for the remaining 75% cities as testing data with leave one out method for cross-validation.

Figure 2 shows the predicted CAV readiness index for the 52 cities. Overall, we observe that the Dallas, Texas region is most ready for CAVs. Further, Figures 3, 4 and5 show the cities readiness with respect to policy, physical, and cyber infrastructure. Different cities lead in each category. Dallas also has the highest policy readiness together with Austin, Seattle and Denver. However, given the policy readiness score of around 0.14 for most of the cities, no city can be declared ready with respect to their policies and regulations measures. Thus, there is a need to devise new policies in order to facilitate CAVs. Physical infrastructure results in Figure 4 suggest that Portland, Oregon is more ready as there are already deploying infrastructure for CAV testing [START_REF]Cav testing site[END_REF]. Similarly we see Phoenex, Arizona among the top five cities with its physical infrastructure ready since this is the city where Waymo is testing its self-driving taxi service [START_REF] Waymo | Self-driving taxi testing location[END_REF].

Finally, Figure 5 shows the cyber infrastructure readiness score for the 52 cities. Dallas, Texas slightly leads with a relatively similar score as other cities.

Overall, we observe that none of the cities exceeds a cyber infrastructure readiness score of 0.2, suggesting the need for measures to be taken by cities in improving their cyber infrastructure to support CAVs.

CONCLUSIONS

The advent of CAVs in future smart cities is likely. There is a lack of study on whether cities are ready for connected and autonomous vehicles or are at the discretion of car manufacturers and technology companies. Therefore, in this paper, we proposed a new readiness index as a measure of current cities readiness towards CAVs. A numerical index is derived from the weighted average of 16 factors with respect to three key elements, a city's policies, its physical and cyber infrastructure. We leveraged decision tree as the machine learning model to predict the readiness index for 52 cities based on the real training data collected from 13 cities in the United States.

Results from the comparison of different cities readiness index show that each city's readiness with respect to different aspects differs with most cities far from ready, though, large cities, for instance, Dallas, Texas with its high resources seems relatively more ready. However, there is still a need for cities to consider improving their policies/regulations, physical infrastructure and in particular their cyber infrastructure in order to facilitate CAVs on their roads.

Figure 1 :

 1 Figure 1: Composition of CAV Readiness Index with each factor's importance weighted by experts shown in parenthesis

Table 1 :

 1 Infrastructure quality normalized w.r.t road network CAVs can easily detect road markings/signage Binary value {0,1} for quality inspection availability High-tech roadside facilities EV charging stations density w.r.t population Accommodate large number of Electric CAVs Value in the interval [0,1] for EV stations ratio CAV compatibility Ratio of CAV compatible infrastructure w.r.t population CAV compatible facilities require low height/space Value in the interval [0,1] for facilities w.r.t population CAV Readiness Index Summary regular inspections scheduled by the transportation department as a binary variable contributing to this factor. 2.2.2 High-tech roadside facilities. A large number of high-tech roadside facilities such as EV charging stations would be required to accomodate CAVs as we expect most CAVs to also be electric vehicles (EVs). Thus, a city is ready for CAVs if it has an abundance of EV charging stations. Abundance is not simply the number of charging stations.

	Factor	Description	Criteria	Rationale	Scoring
		CAV department	Whether a dedicated CAV department exists	Responsible for CAV rules and regulations	Binary value {0,1} for department availability
	Policy	CAV investments	Investment normalized w.r.t population	Facilitate CAV technological development	Binary value {0,1} for available investment
		CAV privileges	Amount of rules to prioritize CAV traffic exist	Incentivize citizens towards CAV usage	Binary value {0,1} if CAV privileges available
		Infrastructure quality
	Physical Infrastructure
		Mobile Network	City-wide High-speed mobile network coverage	High-speed wireless Internet connectivity for CAVs Binary value {0,1} for for mobile Internet availability
	Cyber-Network availability	Vehicular Network	City-wide short-range wireless RSUs density	Facilitate short-range V2X and I2V communication Binary value {0,1} for RSU availability
		Fiber Network	City-wide optical fiber available w.r.t road network	Facilitate RSUs high-speed Internet connectivity	Binary value {0,1} for fiber network availability
		Pedestrian	Whether pedestrian detection technology available	Assist CAV promptly detect pedestrians	Binary value {0,1} for technology availability
	Cyber-Data analytics	Data center 3D Maps	Whether a data center is available Whether 3D maps are available	Accommodate local control center for CAVs Assist CAVs for driving	Binary value {0,1} for data center availability Binary value {0,1} for maps availability
		ITS	Whether an ITS system is available	Assist CAVs for driving	Binary value {0,1} for ITS availability
		Infrastructure security	Whether ITS infrastructure secure	Physical and cyber attacks prevention	Binary value {0,1} for ITS security system availability
	Cyber security	Communication security	Measures to secure communication exist	Jamming and hacking prevention	Binary value {0,1} for secure communication measure availability
		Disaster recovery	Whether a disaster response/recovery system exists	Responsible for recovery after disaster/attack	Binary value {0,1} for disaster recovery system availability

•

  Mobile data network availability: CAVs can use the high speed 4G/LTE or the upcoming 5G technology links provided by the mobile network providers to communicate with the infrastructure network. High-speed Internet connectivity allows them to efficiently send or receive safety critical information to a centralized control center on the go. Therefore, a city-wide mobile network coverage greatly contributes to the CAVs' readiness index. One way of finding this measure is to find Internet coverage or the availability of city-wide Wifi network coverage with respect to different population clusters. In our survey, we inquired regarding the availability of Mobile Internet coverage in the city. The "Impact of having a mobile network" was scored 4.7 by expert policy planners.

	• Vehicular communication technology availability:
	This measure considers the different V2V (Vehicle to Ve-
	hicle) and V2I (Vehicle to Infrastructure) communication
	technology developed till date and the deployment of any
	such technology by the city administration. For instance,
	one measure is to find the amount of deployed Road Side
	Units (RSUs) available in the city with respect to the pop-
	ulation. RSUs are connected to the infrastructure network
	using short or long-range wireless communication technol-
	ogy and can help collect and diffuse data to and from CAVs
	on the roads.Additionally, a city administration can consider
	the total number of registered vehicles equipped with long-
	range (4G/LTE) and short-range V2I communication devices
	enabling local V2V content exchange. We collected data re-
	garding RSUs deployment in each of the considered cities.