Martin Rodriguez-Vega

Carlos Canudas-De-Wit

Hassen Fourati

Joint Flow and Density Reconstruction in Large Traffic Networks Using Partial Turning Ratio Information

We address the recent problem of state reconstruction in large scale traffic networks using heterogeneous sensor data. First, we deal with the conditions imposed on the number and location of fixed sensors such that all flows in the network can be uniquely reconstructed. We determine the minimum number of sensors needed to solve the problem given partial information of turning ratios, and then we propose a linear time algorithm for their allocation in a network. Using these results in addition to floating car data, we propose a method to reconstruct all traffic density and flow. Finally, the algorithms are tested in a simulated Manhattan-like network.

I. INTRODUCTION

The estimation of vehicle occupancy and vehicular flow in traffic networks is crucial for traffic management operators [START_REF] Fourati | Measuring Urban Traffic Congestion -a Review[END_REF]. It allows to monitor the state of different urban areas and to detect traffic congestion. This information can be used to apply control strategies to reduce the impact of high traffic demands.

Network state information can be recovered from heterogeneous data sources. Floating car data (FCD) is available due to the expanded use of GPS-capable devices [START_REF] Fourati | Measuring Urban Traffic Congestion -a Review[END_REF]. This provides the traces of some vehicles which can be used to estimate the mean speed over the entire network. On the other hand, fixed sensors (e.g. magnetic loops) give a reliable measure of the occupancy and traffic flow over a specific location [START_REF] Treiber | Traffic flow dynamics: Data, models and simulation[END_REF]. Furthermore, vehicle re-identification sensors (e.g. Bluetooth and RFID identifiers) located in road intersections can give information about the routing preferences of vehicles [START_REF] Bhaskar | Fundamental understanding on the use of Bluetooth scanner as a complementary transport data[END_REF], which can be used to estimate the turning ratios in monitored places. These could also be inferred from traffic cameras or from previous surveys [START_REF] Hu | Estimation of time-dependent intersection turning proportions for urban signal controls[END_REF].

Budget optimization, which traffic authorities often seek, is related with the problem of finding minimum number of sensors and their locations such that the traffic state is identifiable. This problem has been a recent topic of high interest [START_REF] Gentili | Locating sensors on traffic networks: Models, challenges and research opportunities[END_REF], [START_REF] Viti | Assessing partial observability in network sensor location problems[END_REF]. In some works it has been assumed that turning ratio information is fully available. For instance, in [START_REF] Bianco | A Network Based Model for Traffic Sensor Location with Implications on O/D Matrix Estimates[END_REF], sensors are associated with influence regions whose links are calculated by means of the measured data to provide heuristics on the upper and the lower bounds on the minimum number of sensors. In [START_REF] Lovisari | Density/Flow reconstruction via heterogeneous sources and Optimal Sensor Placement in road networks[END_REF], the sensor location problem is solved via an optimization setup by reducing the propagation of noise when inferring unmonitored links. However, the { martin.rodriguez-vega, carlos.canudas-de-wit }@gipsa-lab.fr * * Univ. Grenoble Alpes, CNRS, INRIA, Grenoble INP, GIPSA-Lab, 38000 Grenoble, France hassen.fourati@gipsa-lab.fr assumption that all turning ratios are known may not be realistic in real world traffic applications.

This has motivated researchers to look at cases where no turning ratios are known. In [START_REF] Hu | Identification of vehicle sensor locations for link-based network traffic applications[END_REF], [START_REF] Ng | Synergistic sensor location for link flow inference without path enumeration: A node-based approach[END_REF] only vehicular flow conservation equations are used to determine bounds on the number of sensors and their locations. The results were improved by [START_REF] Ng | Synergistic sensor location for link flow inference without path enumeration: A node-based approach[END_REF]. They compute the minimum number of sensors and their locations by first expressing the flow relations as under-determined set of linear equations, and then, by operating via the Gaussian elimination method. Unfortunately, the required number of sensors range between 50% and 60% of all links for real traffic networks, which is not possible to achieve under budget constraints.

In parallel, density estimation has also been a field of active research [11]. However, most of the research in this topic has been centered in highways. For urban traffic networks, [START_REF] Lovisari | Density/Flow reconstruction via heterogeneous sources and Optimal Sensor Placement in road networks[END_REF], [START_REF] Zuurbier | Traffic Network State Estimation Using Extended Kalman Filtering and DSMART[END_REF] and [START_REF] Ladino | Density and flow reconstruction in urban traffic networks using heterogeneous data sources[END_REF] have provided methods to recover both flow and density by using turning ratio information in all intersections.

To the best of our knowledge, no results have been provided for density and flow reconstruction in urban traffic networks when turning ratios are only partially known. In this paper, we incorporate partial information of turning ratios to calculate the minimum number of sensors. Additionally, we present a modified version of the algorithms developed in [START_REF] He | A graphical approach to identify sensor locations for link flow inference[END_REF] to use this partial information for the location of sensors. We use the data collected from all different sources to jointly reconstruct flow and density everywhere. We evaluate the proposed algorithms in a simulated traffic network. This work is carried out within the context of the ERC, Scale-FreeBack (see, [START_REF]Scale-Free Control for Complex Physical Network systems. Scale-FreeBack[END_REF]), which aims at developing holistic scale-free modeling, estimation and control methods for controlling complex network systems with application to large scale traffic systems.

II. PROBLEM FORMULATION

Traffic networks are modeled as a directed graph G = {N , E} where nodes N = {1, 2, . . . , n N } represent traffic intersections, and links E = {1, 2, . . . , n E } correspond to roads which are partitioned in three sets: incoming boundary roads E in , internal network roads E net , and outgoing boundary roads E out , with cardinalities n in , n net , n out , respectively. For any k ∈ N , the sets I(k) ⊂ E and O(k) ⊂ E are the links that go in or come out of k, respectively.

In this paper, we consider stationary traffic networks so that flow dynamics are in steady-state. This is formally true only when external boundary flows are constant and the network dynamics reach equilibrium, or it is approximately true when the external boundary flows slowly evolve in time. The reason of this assumption is based on the idea that our density/flow reconstruction can be performed in a fast enough time-scale when compared with the evolution of the natural network dynamics, and therefore the analysis can be carried out using only flow/density equilibrium equations. This assumption substantially simplifies the reconstruction algorithm design, and is typically considered in the literature [START_REF] Gentili | Locating sensors on traffic networks: Models, challenges and research opportunities[END_REF]. Nevertheless, our proposed solution will be tested in a dynamic network simulation.

For every road e ∈ E, we assign scalar variables ρ e , ϕ e , v e representing the equilibrium density, flow, and speed, respectively. We define the turning ratio r e,f ∈ (0, 1] as the proportion of flow from e that is transfered to f if they are connected to the same intersection for which e is incoming and f is outgoing. Otherwise, r e,f = 0.

We assume that traffic flow is a conserved quantity, where the sources are only the elements of E in , and sinks are only the elements of E out . In equilibrium, flow is constant along each road, and there is no accumulation of vehicles. Thus, each intersection k must obey an equation of the form:

e∈O(k) ϕ e - e∈I(k) ϕ e = 0. (1)
The collection of equations for all k ∈ N can be rewritten in matrix notation as L 0 ϕ = 0, where, ∀k ∈ N and ∀e ∈ E, we have

L 0 k,e =    1 if e ∈ O(k) -1 if e ∈ I(k) 0 else . This matrix has dimensions n N × n E .
If knowledge of turning ratios is available, the conservation equations can be rewritten to include this additional information: the outflows of every intersection can be expressed by the sum of inflow contributions weighted by its turning ratios,

ϕ f - e∈I(k) r e,f ϕ e = 0 : ∀f ∈ O(k) (2)
where the turning ratios satisfy the condition f r e,f = 1. Expression ( 2) is only valid for the links that go out from a node in N , so the flow of links belonging to E in cannot be written in this way. Similarly, the flow of links belonging to E out does not contribute to the sum in the second term of the equation.

The ensemble of all equations following (2) is expressed in matrix form as

ϕ net ϕ out -R T ϕ in ϕ net = 0 , where R
is the matrix of turning ratios from the roads in E in ∪ E net to road in E net ∪ E out , and ϕ in , ϕ net , ϕ out are the flows of roads E in , E net , E out , respectively.

To simplify, let F -and F + be selection matrices such that

F -ϕ = ϕ in ϕ net and F + ϕ = ϕ net ϕ out . With this notation, the system of equations is L R ϕ = 0, where L R = F + -R T F -.
It is clear that matrices L 0 and L R represent the flow conservation equations, and that L R contains also contain information about the turning ratios. Note that both matrices have n E columns, but L 0 has only n N rows, while L R has n E -n in rows. Thus a unique solution does not exist. To uniquely reconstruct network flows it is thus required to include additional sensor data such that these systems can be solved.

Let S ⊆ E be the set of roads where flow sensors are located. To represent flow measurements, the sensing matrix C(S) is defined such that the entry (i, e) is 1 if the i-th sensor is present at road e , and 0 otherwise. Flow measurements from sensors are denoted as ϕ m . The selection of a suitable set of measured links S such that a unique reconstruction of the vehicular flow vector ϕ can be obtained is known as the Network Sensor Location Problem (NSLP) [START_REF] Hu | Identification of vehicle sensor locations for link-based network traffic applications[END_REF].

The fundamental diagram is a well-known empirical relation between traffic variables that allows to express flow solely as a function of density: ϕ = Φ(ρ). One of the most popular choices is the triangular fundamental diagram [START_REF] Treiber | Traffic flow dynamics: Data, models and simulation[END_REF]:

Φ(ρ) = v 0 ρ if 0 ≤ ρ ≤ ρ c w(ρ max -ρ) if ρ c ≤ ρ ≤ ρ max , (3)
where v 0 is the free-flow speed, w is the congested wave propagation speed, ρ max is the jam density, and the maximal flow ϕ max occurs at the critical density ρ c . Vehicle speed is calculated as the slope of the line that connects the origin to any point in the diagram [START_REF] Treiber | Traffic flow dynamics: Data, models and simulation[END_REF]. The first linear portion of the function (density below the critical value) receives the name of free-flow regime and is characterized by all vehicles having speed v 0 . The region ρ > ρ c is called the congested regime as vehicles start to interact with each other reducing the average speed of the road. It is not possible to uniquely reconstruct density from either flow or speed alone due to the non-unicity of the inverse of the map Φ -1 (•). For instance, for a measured flow, two values of densities can be found. Likewise, if we only measure speeds, we cannot reconstruct density below its critical value. Thus, to recover the full information it is required to use both speed and flow data. Due to widespread mobile devices, we assume that the mean speed data is available over all links of the network.

Problem statement. Given any traffic network G = {N , E} where turning ratio information is available only for the set R ⊂ N : 1. determine the minimum number of sensors and their locations to solve the NSLP, and 2. use speed data and sensor measurements to estimate flow and density for all roads in the network.

The first part of the problem will be treated in Section III, and the second in Section IV.

III. NETWORK SENSOR LOCATION PROBLEM (NSLP)

The flow conservation equations were expressed for two specific cases: either turning ratios were unknown resulting in matrix L 0 , or the turning ratios were assumed to be known everywhere (matrix L R ). However, in some cases it may be possible that turning ratios are only available at a reduced set of intersections. Denote R ⊆ N as the set of intersections where turning ratio information is known. We define L(R) as the matrix that expresses the conservation equations by using the most information, and such that L(R)ϕ = 0.

To find the structure of this matrix we proceed as follows. Note that L 0 can obtained by making linear combinations of the rows of L R : for each intersection k, there are |O(k)| rows in L R but only one row in L 0 . In an analogue manner, we write

L(R) = J(R)L R , where J(R) = X Y , such
that X is a diagonal matrix defined as

X e,e = 1 if e ∈ k∈R O(k) 0 else , ( 4
)
and Y is such that ∀k ∈ (N \ R) and ∀e ∈ (E net ∪ E out ),

Y k,e = 1 if e ∈ O(k) 0 else . ( 5
)
Matrix J(R) has the effect of combining the rows of L R for which turning ratios are unknown, thus generating an equation following [START_REF] Fourati | Measuring Urban Traffic Congestion -a Review[END_REF]. Rows of L R related to outflows of nodes in R are unmodified.

The NSLP for partially known turning ratios can be split into two steps. First, we determine the minimum number of sensors needed to solve the problem. Then, we propose an algorithm that finds the sensor locations.

A. Minimum number of sensors

To uniquely reconstruct flows, we require the system of equations

L(R) C(S) ϕ = 0 ϕ m (6)
to admit only one solution. Our problem is to find the set S of minimal cardinality n S such that the matrix in the left hand side of ( 6) is full rank.

Lemma 1. Given any traffic network G = {N , E} such that every link e ∈ E is part of a directed path that ends in a link belonging to E out , the minimum number of sensors needed to solve the NSLP is given by

n S = n E -|N \ R| - k∈R |O(k)|. (7)
Proof. Note that from [START_REF] Viti | Assessing partial observability in network sensor location problems[END_REF],

n S = n E -rank{L(R)}. We shall prove that i) rank[J(R)] = |N -R| + k∈R |O(k)| ii) L R is full rank.
To prove i) we will first show that rank{J(R)} = rank{X} + rank{Y }. Then, we show that rank{X} = k∈R |O(k)| and that rank{Y } = |N \ R|. By inspection of (4) and ( 5), a column e of X can only have a nonzero element if there exists an intersection k ∈ R such that e ∈ O(k). On the other hand, a column e of Y can only have a nonzero element if e ∈ O(m) for some intersection m ∈ (N \R). Due to the fact that (N \R)∩R = ∅, column e cannot be simultaneously nonzero for both X and Y . Thus, any nonzero row of Y cannot be written as a linear combination of the rows of X, and vice versa. Now we proceed to show that rank{X} = k∈R |O(k)|. From (4), X is a diagonal matrix and hence, its rank is equal to its number of nonzero elements, which is

| k∈R O(k)| = k∈R |O(k)|, because the sets O(k) are mutually disjoint.
To show that rank{Y } = |N \ R| we follow a similar analysis. Elements Y k,e and Y m,e cannot be simultaneously nonzero if k = m. Thus, all rows of Y are linearly independent, as they cannot be written as linear combinations of the others. As there are |N \R| rows, rank{Y } = |N \R|.

To prove ii) we will show that L R can be written as L R = [A B] where B is an invertible matrix. Recall that L R = F + -R T F -. Without loss of generality, assume that the ordering of E is such that the smaller indexes correspond to E in , followed by E net and ending with E out . Thus, F -= [I nin+nnet 0 (nin+nnet)×nout ] and

F + = [0 (nnet+nout)×nin I nnet+nout ].
Let B a square matrix by selecting the las n net + n out columns of L R . Thus, B = I -RT , such that

R = 0 nnet×nin I nnet 0 nout×nin 0 nout×nnet R.
Note that all diagonal entries of R are 0, and that for each of the first n net rows, the sum of all elements is 1. Thus, ∀e, f ,

|B T e,e | ≥ f =e |B T e,f |, (8)
which means that B T is a weakly diagonally dominant matrix. The rows corresponding to the links E out are only nonzero in the diagonal, and meet [START_REF] Lovisari | Density/Flow reconstruction via heterogeneous sources and Optimal Sensor Placement in road networks[END_REF] with the strict inequality. As every link is part of a path that ends in an element of E out , for every row e there is a chain of nonzero coefficients B T e,a1 , B T a1,a2 , B T a2,a3 , . . . , B T am,f such that f ∈ E out . In [START_REF] Shivakumar | A Sufficient Condition for Nonvanishing of Determinants[END_REF], it was proved that matrices meeting this properties are nonsingular. Thus, B is an invertible matrix and therefore, L R is full-row rank.

As special cases, when R = ∅, the required number of sensors is n S = n E -n N , and when R = N the required number of sensors if n S = n in . This agrees with the results presented in [START_REF] Lovisari | Density/Flow reconstruction via heterogeneous sources and Optimal Sensor Placement in road networks[END_REF], [START_REF] Ng | Synergistic sensor location for link flow inference without path enumeration: A node-based approach[END_REF].

B. Sensor location

Graph-based approaches, such as the one in [START_REF] He | A graphical approach to identify sensor locations for link flow inference[END_REF], have been shown to be useful to solve the sensor location problem. Because of this, we devised the following algorithm that includes the partial information about turning ratios.

Algorithm 1. Sensor location

Inputs: Traffic network graph G = {N , E}; set of R intersections with turning ratio information.

Output: Subset of measured links S.

1) Generate a virtual node k 0 and connect entering and exiting external flows to it. 2) For each k ∈ R: arbitrarily select all but one of the outgoing links of k and remove them from the graph, such that the resulting graph is connected. Denote the removed links as E R . 3) Construct a spanning tree from the remaining graph, and denote E u as the set of links contained in the tree. 4) Locate sensors as S = E -(E R ∪ E u ): links that were not removed in Step 2 and that are not part of the tree.

This algorithm presents an heuristic modification to the work of [START_REF] He | A graphical approach to identify sensor locations for link flow inference[END_REF] such that turning ratios are included. In the case R = ∅ the two algorithms are equal.

It is important to remark that this algorithm locates exactly the same number of sensors as indicated by the lemma in Section III-A. By adding node k 0 in Step 1, a strongly connected graph with n N + 1 nodes and n E links is obtained [START_REF] Tascikaraoglu | PointQ model of an arterial network: calibration and experiments[END_REF]. Then, Step 2 removes a total of k∈R |O(k)| -|R| links. The input to Step 3 is a connected graph with n N + 1 nodes. From graph theory, any spanning tree made from this graph will have n N links. Therefore, the number of links that do not make part of the tree is n E -k∈R |O(k)|+|R|-n N , which is equivalent to the expression in [START_REF] Bianco | A Network Based Model for Traffic Sensor Location with Implications on O/D Matrix Estimates[END_REF].

The rationale of the algorithm is to locate sensors such that they generate linearly independent rows in [START_REF] Viti | Assessing partial observability in network sensor location problems[END_REF]. It has been shown in [START_REF] He | A graphical approach to identify sensor locations for link flow inference[END_REF], [START_REF] Tascikaraoglu | PointQ model of an arterial network: calibration and experiments[END_REF], [START_REF] Castillo | Non-planar hole-generated networks and link flow observability based on link counters[END_REF] that a basis for the null space of L 0 can be obtained from the cycle space of the graph. If sensors are located in links such that their removal causes the graph to be cycle-free, then the dimension of the null space is reduced to 0 and flow can be reconstructed. Our contribution is focused on Step 2, which is an heuristic that allows to eliminate the selection of rows that are linearly dependent due to the knowledge of the turning ratios. Putting sensors in several outgoing links of an intersection may give redundant information, as their flows can be calculated by the knowledge of incoming links. In Step 3, all the remaining cycles of the graph are removed by constructing a spanning tree, which is an optimal cycle-free structure. Note that spanning trees are not unique, but because the graph is unweighted, all of them are equally possible for the problem at hand. Example: Consider the traffic network shown in Fig. 1a. This graph has n N = 6 intersections and n E = 17 roads. Additionally, E in = {1, 2, 3}, E net = {4, 5, . . . , 13}, and E out = {14, 15, 16, 17}. Turning ratios are known at intersections R = {1, 3}. From Lemma 1, the minimum number of required sensors is n S = 17-(6-2)-(3+3) = 7.

To locate the sensors, we use Algorithm 1:

• Step 1: add the virtual node which makes the graph strongly connected (Fig. 1b). • Step 2: select links 5 and 6 from node 1, and links 10 and 11 from node 3 and remove them from the graph, as shown with dotted gray lines in Fig. 1c. Define E R = {5, 6, 10, 11}. • Step 3: construct a spanning tree from the links (E \E R ).

The tree links are E u = {1, 4, 8, 9, 14, 17} shown with the black solid lines in Fig. 1d.

• Step 4: locate sensors in links S = E \ (E R ∪ E u ) =
{2, 3, 7, 12, 13, 15, 16}. This links are shown with blue dashed lines in Fig. 1d. Finally, note that the number of sensors is |S| = 7, which is in agreement with the previous results.

IV. JOINT DENSITY AND FLOW RECONSTRUCTION

To be able to calculate density from flow, we transform the nonlinear relation (3) into a set of linear equations using speed information. We define a selection function S(v), such

S(v e ) = 1 if v 0 -v e < 0 else , (9)
where is a tunable parameter. Then, an expression for the density at each link is

ρ e = S(v e ) ϕ e v 0 + [1 -S(v e )] ρ max - ϕ e w ,
which can be written in matrix form as ρ = W (v)ϕ + d(v) where ∀e ∈ E,

W e,e (v) = 1/v 0 if v 0 -v e < -1/w if v 0 -v e ≥ is a diagonal matrix, and
d e (v) = 0 if v 0 -v e < ρ max if v 0 -v e ≥ is a vector.
The joint density-flow reconstruction can thus be formulated as a quadratic optimization problem subject to linear constraints:

min φ, ρ W (v) -I C(S) 0 φ ρ - d(v) ϕ m 2 s.t. L(N R ) φ = 0, 0 ≤ φ ≤ ϕ max , 0 ≤ ρ ≤ ρ max , (10)
where ρ and φ are the estimated quantities.

V. NUMERICAL EXAMPLE

To evaluate the proposed method, we considered the simulated traffic network shown in Fig. 2, which is a Manhattangrid with 100 intersections and 220 roads. Turning ratios are selected to be known at 40% of the intersections chosen randomly.

As discussed in Section II, the proposed method considers steady-state networks. However, in real traffic applications this is generally very hard to achieve. For this purpose, we tested the performance of the algorithms under time-varying conditions. To generate synthetic dynamic traffic data we use the well-known Cell Transmission Model (CTM) [START_REF] Daganzo | The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory[END_REF], which is a discretization of the Lighthill-Williams-Richards (LWR) first order traffic model:

ρ e (t + 1) = ρ e (t) + ∆t L ϕ up e (t) -ϕ down e (t) , ( 11
)
where t is the discrete time index, ∆t is the simulation step time, L is the road length, and ϕ up e , ϕ down e are the upstream and downstream flows in link e ∈ E, respectively. At intersections, flows are determined using the junction model presented in [START_REF] Garavello | Models for Vehicular Traffic on Networks[END_REF], [START_REF] Daganzo | The cell transmission model, part II: Network Traffic[END_REF] such that the intersection's throughput (sum of all flows) is maximized while also respecting the turning ratios. The traffic network parameters are shown in Table I. The time step was chosen such that L/∆t > v 0 to satisfy the CFL condition [START_REF] Garavello | Models for Vehicular Traffic on Networks[END_REF].

To initialize the traffic network, a first simulation with constant input flows was run until equilibrium was obtained. Afterwards, each of the boundary input flows was subject to sinusoidal variations:

ϕ ext e = ϕ ss + A sin(ωt) , ∀e ∈ E in ,
where ϕ ss was the flow value obtained for the steady-state initial simulation, the amplitude A = 0.25ϕ max was chosen such that the input flows would reach ϕ max , and ω is an arbitrary frequency. Several runs of the algorithm were made by modifying the value of ω, such that it followed different scenarios of real world traffic patterns, where the associated periods vary between 5 minutes and 6 hours.

To evaluate the algorithm's performance over time, we calculate the normalized root mean square error (NRMSE) of the density along all links in the network relative to the maximum values:

N RM SE ρ (t) = 1 ρ max 1 n E n E e=1 (ρ e (t) -ρe (t)) 2 .
An analogous expression is used to calculate N RM SE ϕ (t) relative to flow.

A. Results and discussion

With the partial knowledge of turning ratios in the considered scenarios, 80 fixed flow sensors are needed, which represents 36% of all the links. This is an improvement in comparison with the case when turning ratios are unknown, which requires 120 sensors (55% of the links). Furthermore, the case when turning ratios are fully known locates only 20 sensors (9%), albeit with the requirement of knowing turning ratios in 60 additional intersections.

Figure 3 shows the obtained RMSE for both density and flow for three different scenarios of varying input frequency, with corresponding periods of 10 minutes, 1 hour and 6 hours. Through all cases, spikes of high and low errors can be associated with the regions of maximum and minimum derivative of the input. As the traffic propagates in the network, roads will follow the input but with phase differences. The blue dashed line shows the case with period of 10 minutes, whose rate of change is faster than traffic propagation in the network. Steady-state conditions are almost never achieved and the total error ranges from 5% to 30%. By increasing the period to 1 hour (red dotted line), the overall error is reduced, and the network can reach equilibrium-like state when the input's time-variation is small. Nevertheless, when the time derivative of the input is steep, error peaks of 20% are obtained. For the case with period of 6 hours shown with a continuous yellow line, errors are below 15% for flow and below 5% for density. Error minima of 0% show that input variations can be sufficiently constant to provide network equilibrium.

VI. CONCLUDING REMARKS

In this paper, we study and solve the network sensor location problem and joint flow and density reconstruction for large scale traffic networks by considering partial information of turning ratios. It is shown that this information can be used to effectively reduce the minimum number of required sensors, and a heuristic algorithm for their locations is proposed. In addition, flow sensor measurements and floating car data (speed measurements) are incorporated in an optimization problem that allows to reconstruct flows and densities for all roads in a traffic network. The proposed methods were evaluated in a simulated Manhattan grid. The results show that, even when the assumption that the network is in equilibrium state is not met, the algorithms find reasonable close results compared to the real values.

Future research on this aspect involves the reconstruction of the traffic state while taking into account network dynamics. Other future works include the development of methods to place sensors in optimal when budget constraints forces the use of less sensors than the minimum number determined in this paper.

  Addition of k0.

  Removal of links in E R .

  Dashed lines contain sensors. Black lines are a tree.

Fig. 1 :

 1 Fig. 1: Example of Algorithm 1 that it identifies the current linear zone of the fundamental diagram:

Fig. 2 :

 2 Fig. 2: Manhattan grid with 100 intersections. Square red nodes represent intersections where turning ratios are known and blue points correspond to unmeasured intersections. Circled green links represent the location of sensors.

Fig. 3 :

 3 Fig. 3: NRMSE for flow and density reconstruction for different input flow variation frequencies.

TABLE I :

 I Parameters used for the simulations

	Variable	Symbol Value	Units
	Road length	L	500	m
	Time step	∆t	15	s
	Free-flow speed	v 0	50	km/h
	Max density	ρmax	125	veh/km
	Max flow	ϕmax	1980	veh/h
	Critical density	ρc	39.6	veh/km
	Congested wave speed	w	23.18	km/h

ACKNOWLEDGEMENTS

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement 694209), see [15].


Among the antecedents of achievement goal endorsement in sports, competition is a consistent predictor of other-approach goal endorsement (trying to perform better than other players). However, most of this previous research was conducted in a context implying a strong focus on normative social comparison. We argue that in other competitive contexts, where both social comparison and temporal comparison are salient, competition can affect players' self-approach goals (trying to perform better than one has done in the past) rather than other-approach goals. Two experiments were conducted with golf players. Results showed that when an intrapersonal standard was salient (e.g., "handicap competition"), golf competition increased self-approach but not other-approach goal endorsement. However, when interpersonal-standard is made salient (e.g., match-play competition), golf competition increased otherapproach goal endorsement. Limits and future perspectives are discussed.

Introduction

Competition, as a central component of sports, influences various outcomes [START_REF] Cooke | The effects of individual and team competitions on performance, emotions, and effort[END_REF][START_REF] Jones | Development and validation of the sport emotion questionnaire[END_REF][START_REF] Stanne | Does competition enhance or inhibit motor performance: A meta-analysis[END_REF]van de Pol, Kavussanu, & Ring, 2012b). The most prototypical forms of competition involve an opposition between at least two people (or teams) for a reward, with one individual (or one team) who wins and one who loses. That is, there is a negative (achievement) outcome interdependence [START_REF] Murayama | The competition-performance relation: A meta-analytic review and test of the opposing processes model of competition and performance[END_REF]van de Pol & Kavussanu, 2012). In such competitive contexts, individuals' competence is defined relative to others; the more competent one will be the winner. A great deal of research has examined motivational processes involved in such contexts [START_REF] Harwood | Assessing achievement goals in sport: Caveats for consultants and a case for contextualization[END_REF][START_REF] Murayama | The competition-performance relation: A meta-analytic review and test of the opposing processes model of competition and performance[END_REF]van de Pol, Kavussanu, & Ring, 2012a;van de Pol et al., 2012b;van de Pol & Kavussanu, 2011, 2012). But, in competition, is one's competence always defined in comparison to others' performance? According to [START_REF] Murayama | The competition-performance relation: A meta-analytic review and test of the opposing processes model of competition and performance[END_REF], a distinction can be made between intrapersonal and interpersonal competition. The main difference between these two kinds of competition is the standard of comparison used to determine competence. In interpersonal competition, what matters is outperforming others; thus, competence is defined based on social comparison with others. In intrapersonal competition, what matters is self-improvement that is, the comparison between previous and current performance (i.e., temporal comparison). Thus far, research on the motivational processes of competition has examined contexts that mainly involved the social comparison process (e.g., football, tennis,...). The purpose of the present research is to examine motivational processes in a domain that also strongly involves temporal comparison: The amateur golf domain. Indeed, classic golf competitions imply both interpersonal and intrapersonal forms of competition. In particular, in classic golf competition, to increase one's index of competence (i.e., the handicap), one has to attain a relative standard of performance (i.e., a number of shots) that is better than one's previous performances (regardless of other players' performances). Thus, in this kind of competition, even if comparison with others is still possible, the need to self-improve is particularly salient.

Achievement Goal Theory

Sports' motivation and the achievement goal theory share a long common story (for a review see [START_REF] Duda | Motivation in sport. The relevance of competence and achievement goals[END_REF], and recent work largely contributes to continuing this tradition [START_REF] Dewar | Achievement goals and emotions in golf: The mediating and moderating role of perceived performance[END_REF][START_REF] Kavussanu | The effects of achievement goals on performance, enjoyment, and practice of a novel motor task[END_REF][START_REF] Morris | Antecedents of approach-avoidance goals in sport[END_REF][START_REF] Sachau | Goal orientation of recreational golfers[END_REF][START_REF] Stenling | Implicit beliefs of ability, approach-avoidance goals and cognitive anxiety among team sport athletes[END_REF]van de Pol et al., 2012avan de Pol et al., , 2012b;;[START_REF] Vansteenkiste | Examining correlates of Game-to-Game variation in volleyball players' achievement goal pursuit and underlying autonomous and controlling reasons[END_REF]. According to this literature, goals depend on the standard used to define competence. Elliot and his colleagues [START_REF] Elliot | A 2 × 2 achievement goal framework[END_REF][START_REF] Elliot | A 3 × 2 achievement goal model[END_REF][START_REF] Elliot | On the measurement of achievement goals: Critique, illustration, and application[END_REF] have argued that three types of standards can be used to define competence: the absolute standard (task mastery), the intrapersonal standard (one's past performances), and the normative standard (the performance of others). Furthermore, goals can also be classified depending on their valence -namely, depending on whether they are focused on the approach of positive outcomes (i.e., succeeding in a competition) and/or on the avoidance of negative outcomes (i.e., avoiding failure). Thus, according to the most recent model of achievement goals [START_REF] Elliot | A 3 × 2 achievement goal model[END_REF], people can pursue six types of goals: self-approach goals (i.e., doing better than before), self-avoidance goals (i.e., avoiding doing worse than before), other-approach goals (i.e., doing better than others), other-avoidance goals (i.e., avoiding doing worse than others), task-approach goals (i.e., doing the task correctly) and task-avoidance goals (i.e., avoiding doing the task incorrectly). Adopting these different achievement goals has consequences on several outcomes in the sports domain [START_REF] Biddle | Correlates of achievement goal orientations in physical activity: A systematic review of research[END_REF][START_REF] Kavussanu | The effects of achievement goals on performance, enjoyment, and practice of a novel motor task[END_REF][START_REF] Stenling | Implicit beliefs of ability, approach-avoidance goals and cognitive anxiety among team sport athletes[END_REF] including in the golf area (e.g., emotions, [START_REF] Dewar | Achievement goals and emotions in golf: The mediating and moderating role of perceived performance[END_REF]learning, Thill &[START_REF] Thill | Learning to play golf under different goal conditions: Their effects on irrelevant thoughts and on subsequent control strategies[END_REF]performances, van de Pol et al., 2012b).

Antecedents of Achievement Goals

Extensive research in the achievement goal field sought to identify which characteristics lead individuals to endorse achievement goals. Among these ones, researchers identified individual characteristics such as perceived competence, perceived motivational climate [START_REF] Morris | Antecedents of approach-avoidance goals in sport[END_REF] or fear of failure [START_REF] Conroy | Fear of failure and achievement goals in sport: Addressing the issue of the chicken and the egg[END_REF]. However, research also identified several contextual factors which influence achievement goal endorsement in the sports domain [START_REF] Chalabaev | Do achievement goals mediate stereotype threat?: An investigation on females' soccer performance[END_REF]van de Pol et al., 2012b;van de Pol & Kavussanu, 2012). In particular, van de Pol and colleagues (2011, 2012a, 2012b) have recently documented that in a competition condition (implying the social comparison process), participants reported more other-approach goals (i.e., called ego goals in those studies) than in a training condition (see also [START_REF] Harwood | Assessing achievement goals in sport: Caveats for consultants and a case for contextualization[END_REF][START_REF] Murayama | The competition-performance relation: A meta-analytic review and test of the opposing processes model of competition and performance[END_REF]. This result might be explained by the fact that, in interpersonal competitive settings (defined by negative outcome interdependence), social comparison information is very salient and drives people to estimate their level of competence on the basis of a normative standard [START_REF] Van Yperen | The overpowering effect of social comparison infor-mation: On the misalignment between mastery-based goals and self-evaluation criteria[END_REF].

Particularity of Amateur Golf Competition

As developed thus far, most of the aforementioned research on the contextual antecedents of achievement goals has been conducted in areas in which social comparison is salient. In such contexts, competition is undoubtedly a predictor of other-approach goals [START_REF] Murayama | The competition-performance relation: A meta-analytic review and test of the opposing processes model of competition and performance[END_REF]van de Pol et al., 2012avan de Pol et al., , 2012b;;van de Pol & Kavussanu, 2011, 2012) but not of self-approach goals (see, for example, van de Pol et al., 2012a). However, would the same effect be obtained in a domain in which competence is also defined through an intrapersonal standard? In amateur golf competition, players' handicap (i.e., players' index of competence) is at stake. Players' handicap evolves after each competition based on a comparison between one's current and past performances. If a player does better than s-he did in the past, the handicap decreases, whereas if the player plays worse, the handicap increases. Thus, the lower the handicap, the better a player is.

In golf competition, the handicap is thus particularly important, even if comparison with other players is still present. As a consequence, we argue that, in this context, others are less relevant sources of information to determine one's own level of competence than in other forms of more traditional competition. Indeed, as golf players mainly anticipate self-referenced feedback, past performance may be a more relevant source of information than others' performances to conclude on whether one has, or has not, performed well. Thus, in this very domain, self-approach goals should be the most relevant goals to endorse. As a support to this idea, research has shown that when a self-referenced feedback is expected, students endorse more self-referenced goals than when a normative feedback is expected [START_REF] Butler | Are mastery and ability goals both adaptive? Evaluation, initial goal construction and the quality of task engagement[END_REF][START_REF] Pekrun | The power of anticipated feedback: Effects on students' achievement goals and achievement emotions[END_REF].

Consequently, we hypothesize that, in the amateur golf context, competition would increase selfapproach goal endorsement, but not other-approach goal endorsement, as compared to a no-competition condition. Experiment 1 tested this hypothesis by comparing goal endorsement in a competition condition (expected to make salient, by default, the intrapersonal standard) and a no-competition condition. Experiment 2 went a step further by making explicit either the intrapersonal standard or the interpersonal standard of the competition. Thus, Experiment 2 compared golf players' goal endorsement in three conditions: a no-competition condition, and two competition conditions, one that made salient the intrapersonal standard and another that only focused on the interpersonal standard. An increase of self-approach goal endorsement is expected only for participants in the intrapersonal standard competition condition, and an increase of other-approach goals is only expected for participants in the strictly interpersonal standard competition condition, as in previous research [START_REF] Murayama | The competition-performance relation: A meta-analytic review and test of the opposing processes model of competition and performance[END_REF]van de Pol, et al., 2012avan de Pol, et al., , 2012b;;van de Pol & Kavussanu, 2011, 2012). It is worth noting that there is a debate toward the inclusion of the avoidance components of achievement goals in sport motivation (see [START_REF] Duda | Motivation in sport. The relevance of competence and achievement goals[END_REF][START_REF] Roberts | Understanding the dynamics of motivation in sport and physical activity. An achievement goal interpretation[END_REF]. This can probably explain why avoidance goals were not studied in most previous research [START_REF] Harwood | Assessing achievement goals in sport: Caveats for consultants and a case for contextualization[END_REF]van de Pol et al., 2012avan de Pol et al., , 2012b;;van de Pol & Kavussanu, 2011, 2012). That is also the reason why our hypotheses focused on the approach form of achievement goals. However, as outside of the sport field, other-avoidance goal endorsement has been shown to be impacted by competition (i.e., on a verbal task, see [START_REF] Murayama | The competition-performance relation: A meta-analytic review and test of the opposing processes model of competition and performance[END_REF], results for self-avoidance and other-avoidance goals are also reported here.

Experiment 1

Method Participants

One hundred and ninety-four French golf players participated in an online experiment and completed the questionnaire (31 women, 163 men), with a mean age of 49.33 years (SD = 15.24), a mean handicap of 24.21 (SD = 13.32) and a mean experience of 8.98 years (SD = 8.02) within the golf domain.

Materials and procedure

After receiving the agreement from several golf associations, their members were invited by e-mail to participate in an online experiment about their golf practice -a participation that could allow them to take part in a lottery. Players who were interested in participating to the experiment clicked on a link, received information regarding their rights in the experiment, and had to give their consent before completing the questionnaire. An institutional ethics committee approved the experimental protocol before data collection began. If participants finally did not consent, they were automatically redirected to an ending page without any further possibility to take part in the experiment. If they gave their consent, participants were randomly assigned to either a competition (N = 98) or a no-competition condition (N = 96). Experimental conditions were introduced with the instructions of the questionnaire. Participants in the no-competition condition read: "The following sentences refer to the different kinds of goals that you might pursue when you play with your friends, without competition. Please indicate to what extent each statement is true for you during your friendly games". Participants in the competition condition read: "The following sentences refer to the different kinds of goals that you might pursue when you play for competition. Please indicate to what extent each statement is true for you during the competition." Participants then answered the achievement goals questionnaire and provided demographic information (e.g., age, handicap, frequency of playing). Participants were randomly assigned to one of the two conditions. Preliminary analyses confirmed that participants of the two conditions did not differ in term of age, frequency of playing and handicap (all F < 2, ns).

Measures

Achievement goals questionnaire. The achievement goals questionnaire [START_REF] Elliot | A 3 × 2 achievement goal model[END_REF] was translated into French first and then back-translated into English. This questionnaire was adapted to fit golf practices. Participants answered on a 7-point scale, ranging from 1 "Not at all true for me" to 7 "Very true for me" (e.g. for self-approach goals, "To perform well relative to how well I have done in the past"; for self-avoidance goals, "To avoid performing worst than I normally do"; for other-approach goals, "To do well compared to others players"; for other-avoidance goals, "To avoid doing worse than others players"). Descriptive statistics, reliability, and correlations are reported in Table I. Of importance, reliability indicators were good and very close to those reported in [START_REF] Elliot | A 3 × 2 achievement goal model[END_REF].

Results

To test whether players in the competition condition would endorse more self-approach goals than those in the no-competition condition, whereas no differences would be found for other-approach goal endorsement, ANOVAs were run on each type of achievement goals. The model integrated one predictor, the competition condition (coded -1 for no-competition and +1 for competition). Since the handicap has previously been linked to achievement goal endorsement [START_REF] Sachau | Goal orientation of recreational golfers[END_REF], in the two experiments, additional analyses included the handicap as a control variable. Including handicap did not change the effects. Therefore, this variable was removed from the analysis. Means and standard deviations by experimental conditions are presented in Table II.

Self-approach goals

As expected, a main effect of the experimental condition, F(1,192) = 5.30, p = .022, η p 2 = .02, indicated that participants in the competition condition (M = 5.71, SD = 1.08) endorsed more self-approach goals than participants in the no-competition condition (M = 5.34, SD = 1.19).

Self-avoidance goals

A marginal effect of the experimental condition, F(1,192) = 3.85, p = .051, η p 2 = .02 showed that in the competition condition (M = 5.36, SD = 1.20), participants tended to endorse more self-avoidance goals than in the no-competition condition (M = 4.98, SD = 1.47).

Other-approach goals

The competition effect was not significant, F(1,192) < 1, ns. Participants in the competition condition (M = 4.50, SD = 1.66) did not endorse more other-approach goals than participants in the no-competition condition (M = 4.42, SD = 1.80).

Other-avoidance goals

There was no difference between the two conditions, F(1,192) < 1, ns. Participants in the competition condition (M = 4.28, SD = 1.68) did not differ in their other-avoidance goal endorsement as compared with participants in the no-competition condition (M = 4.32, SD = 1.74). In competitive settings, the main evaluative referent for competence can be either the self or others, but rarely the absolute demand of the task. Since task-based goals are not particularly relevant in such contexts, there are few reasons to expect task-based goals to be impacted by competition. However, as these goals are part of the 3 x 2 model [START_REF] Elliot | A 3 × 2 achievement goal model[END_REF], task-based goals were also measured in this experiment. Results showed that competition did not impact task-approach goal, F(1,192) = 2.38, p = .13, or task-avoidance goal endorsement, F(1,192) < 1.

Discussion

As expected, players in the competition condition reported a higher level of self-approach goals than players in the no-competition condition, whereas no difference was found between conditions for otherapproach goal endorsement. Also, competition tended to impact self-avoidance goal endorsement but not other-avoidance goal endorsement. Taken together, results provide preliminary evidence that in the context of amateur golf, where individual's competence is strongly defined through an intrapersonal standard, self-approach goals seem to be more relevant than other-approach goals.

It should be noted that our interpretation of these findings relies on the assumption that in the context of the present research -the amateur golf domain -competition puts the emphasis on an intrapersonal standard to define competence. But, in some instances, golf can also involve strictly interpersonal competition, as in the research of van de Pol et al. (2012b). Indeed, although usual weekly competitions do not strongly focus on normative comparison, some other kinds of golf competitions do (e.g., matchplay competition). In match-play competition, two players are opposed with the purpose of making the lowest score on a hole to get one point. The winner is the player who has most points. In such contexts, competition would probably enhance, as in previous research, other-approach goals more than selfapproach goals. In Experiment 1, the instructions did not explicitly emphasize the type of competition at stake: a competition for one's handicap (i.e., an intrapersonal-standard competition) or a match-play competition (i.e., a strictly interpersonal-standard competition). Results of Experiment 1 support the idea that, by default, golf competition emphasizes an intrapersonal standard. However, would the same results appear on a competition that would emphasize interpersonal standard rather than intrapersonal standard? Experiment 2 was designed to address this question. In this experiment, the type of standard at stake for the competition (i.e., intrapersonal vs. interpersonal) was directly manipulated. Experiment 1's finding on self-goals should be replicated in a competition condition that makes explicit the importance of intrapersonal standard (i.e., the handicap), but not in a competition condition that involves an interpersonal standard (i.e., match-play).

Experiment 2

Experiment 2 sought to replicate Experiment 1's findings with an explicit manipulation of the two different types of competition. More precisely, we expected players in the handicap competition condition to endorse more self-approach goals compared with those in the no-competition and matchplay conditions. The rationale behind this hypothesis is that it is only in the handicap condition, but not in the two other conditions, that improving is particularly valued and rewarded. Regarding otherapproach goals, based on past research, comparison with others should be most salient in the matchplay context, but less so otherwise. Accordingly, we expected players in the match-play competition condition to endorse more other-approach goals than players in the no-competition and in the handicap conditions. Contrasts were coded (see below in the Results section) to reflect these specific hypotheses.

Method Participants

Two hundred and eighty-three French golf players (56 women, 227 men), with a mean age of 57.37 years (SD = 11.56), a mean handicap of 23.00 (SD = 11.01) and a mean experience of 12.37 years (SD = 8.61) within the golf domain, participated in an online experiment and completed the questionnaire.

Materials and procedure

Participants were recruited in the same way as in the first experiment and also had the opportunity to participate to a lottery. As previously, prior to the experiment, participants had to give their consent and were then randomly assigned to the handicap competition (n = 98), the match-play competition (n = 91) or the no-competition condition (n = 94). As in the first experiment, it should be noted that there were no differences between participants in the three conditions in term of frequency of playing or their handicap (all F <2, ns). A significant difference appeared on age, F( 2 Measures Achievement goals questionnaire. The same measure from Experiment 1 was used in this second experiment, with descriptive statistics, reliability, and correlations reported in Table III.

Results

Data analyses

Data were analyzed using contrast analyses. This procedure allows testing specific hypotheses when there are more than two levels in the independent variable [START_REF] Judd | Data analysis: Continuing issues in the everyday analysis of psychological data[END_REF]. With this procedure, a contrast of interest, which tests the hypothesis, and an orthogonal contrast, which tests the residual variance, should be defined. The contrast of interest should be significant, and the orthogonal contrast should not. If the orthogonal contrast is significant, it means that the contrast of interest does not explain all the variance, namely, that the orthogonal contrast also contributes to explain variance in the data. Means are reported in Table IV.

Contrast coding and results for self-based goals

Participants in the handicap condition were expected to report a higher level of self-approach (and selfavoidance) goals than in the two other conditions (i.e., match-play and no-competition). Thus, the contrast of interest compared the handicap condition (coded 2) with the match-play and the control conditions (coded -1 each). The orthogonal contrast compared the match-play condition (-1) to the control condition (1), with the handicap condition coded 0.

Self-approach goals. The contrast of interest was significant, F(1,280) = 12.08, p = .001, η p 2 = .04, indicating that participants in the handicap condition (M = 5.45, SD = 1.06), endorsed more selfapproach goals than participants in the match-play (M = 4.76, SD = 1.23), and the no-competition conditions (M = 5.09, SD = 1.29). The analysis also revealed a marginal effect of the orthogonal contrast: participants in the match-play condition tended to endorse less self-approach goals than participants in the no-competition condition, F(1,280) = 3.44, p = .065, η p 2 = .01.

Self-avoidance goals. The contrast of interest examining the handicap competition in opposition to the match-play and the no-competition conditions was not significant, F(1,280) < 1, nor was the orthogonal contrast, F(1,280) = 1.20, ns.

Contrast coding and results for other-based goals

Participants in the match-play condition were expected to report a higher level of other-approach (and other-avoidance) goals than in the two other conditions. Thus, the contrast of interest compared the match-play condition (coded 2) with the handicap and the no-competition conditions (coded -1 each). The orthogonal contrast compared the handicap condition (-1) to the no-competition condition (1) with the match-play condition coded 0.

Other-approach goals. The contrast of interest was significant, F(1,280) = 22.52, p <.001, η p 2 = .07, indicating that participants in the match-play condition (M = 4.91, SD = 1.28), endorsed more otherapproach goals than participants in the handicap (M = 3.54, SD = 1.84), and the no-competition condition (M = 4.40, SD = 1.48). Analyses also revealed a main effect of the orthogonal contrast showing that participants in the handicap condition endorsed less other-approach goals than participants in the nocompetition condition, F(1,280) = 14.37, p <.001, η p 2 = .04.

Other-avoidance goals. The contrast of interest examining the match-play competition condition in opposition to the handicap competition and the no-competition conditions was significant, F(1,280) = 24.24, p < .001, η p 2 = .08, indicating that participants in the match-play condition (M = 4.74, SD = 1.25), endorsed more other-avoidance goals than participants in the handicap (M = 3.31, SD = 1.73), and the no-competition conditions (M = 4.25, SD = 1.58). Nevertheless, the analysis also revealed an effect of the orthogonal contrast showing that participants in the handicap condition endorsed less other-avoidance goals than participants in the no-competition condition, F(1,280) = 18.10, p < .001, η p 2 = .06. As in experiment 1, task-based goals were measured. Results showed a main effect of the experimental condition on task-approach goal endorsement, F(2,280) = 10.82, p< .001, η p 2 = .07, with participants in the match-play competition condition (M = 5.25, SD = 1.11) endorsing less task-approach goals than participants in the handicap competition (M = 5.71, SD = 0.93) and the no-competition condition (M = 5.89, SD = 0.85). Regarding task-avoidance goals, the experimental condition did not affect their endorsement, F(2,280) < 1. As these goals were not the focus of the present paper, these results will not be discussed further.

Discussion

Experiment 2 aimed at extending and clarifying Experiment 1's findings via a direct manipulation of the type of standard at stake in the competition (handicap versus match-play). As expected, results demonstrated that the increase in self-approach goals observed in Experiment 1 was restricted to the handicap competition condition, with no such increase obtained in the match-play competition condition. Moreover, in accordance with previous findings and further supporting the specificity of the default amateur golf competition context of the present research, an increase in other-approach goals was observed in the match-play competition condition, but not in the handicap competition condition.

General discussion

Previous research has identified competition as an important and consistent predictor of other-approach goal endorsement [START_REF] Murayama | The competition-performance relation: A meta-analytic review and test of the opposing processes model of competition and performance[END_REF]van de Pol et al., 2012avan de Pol et al., , 2012b;;van de Pol & Kavussanu, 2011, 2012). Because amateur golf competition also implies a strong focus on self-improvement and temporal comparison, we hypothesized that self-approach goals should be more relevant than otherapproach goals in this very context. In such a context, we therefore expected competition to lead golf players to specifically endorse more self-approach goals as compared to a no-competition condition, but not to increase endorsement of other-approach goals.

Results from two studies confirm these hypotheses. First, Experiment 1 showed that an unspecified competition condition in an amateur golf setting increased self-approach goal endorsement but did not impact other-approach goal endorsement. The second experiment demonstrated that when the type of golf competition (match-play vs. for the handicap) was explicitly specified, both previous findings from the literature (in the match-play competition condition only) and Experiment 1's results were replicated (in the handicap com-petition condition only). Indeed, results from Experiment 2 showed that matchplay competition increased other-approach goal endorsement but not self-approach goal endorsement, as in previous research (van de Pol et al., 2012ade Pol et al., , 2012b;;van de Pol & Kavussanu, 2011, 2012). Instead, golf competition for the handicap elicited higher self-approach goals endorsement, as in Experiment 1. Moreover, Experiment 2 demonstrated that other-approach goals in the handicap competition condition and self-approach goals in the match-play competition condition were less adopted than in the nocompetition condition, confirming, in a complementary way, that these two different types of goals are selectively less adopted if they do not match the most relevant standard of comparison.

Although our focus was on the approach dimension of achievement goals, as previously done in the sports domain [START_REF] Harwood | Assessing achievement goals in sport: Caveats for consultants and a case for contextualization[END_REF]van de Pol et al., 2012avan de Pol et al., , 2012b;;van de Pol & Kavussanu, 2011, 2012) and, hence pro-viding a background for specific hypothesis testing, we also assessed the avoidance dimension of achievement goals. Confirming the rather exploratory nature of the competition avoidance achievement goal relation in sports, results for self-avoidance goal endorsement were somewhat inconsistent across the two studies. Indeed, whereas Experiment 1 showed that the competition condition, compared with the no-competition condition, led players to marginally endorse more selfavoidance goals, results from experiment 2 did not confirm these findings. Results for other-avoidance goal endorsement were more consistent. As for other-approach goal endorsement, in Experiment 1, the endorsement of other-avoidance goals was not affected by the competition condition, and in the second experiment, other-avoidance goal endorsement was elicited in the match-play competition condition and reduced in the handicap competition condition. These results conceptually replicate, in a different domain, those from [START_REF] Murayama | The competition-performance relation: A meta-analytic review and test of the opposing processes model of competition and performance[END_REF] who showed that students in an interpersonal competition condition endorsed more other-avoidance goals than students in a control condition.

Taken together, results of the present research provide evidence that competition does not necessarily and systematically involve other-approach goal endorsement, as it has been shown in past research [START_REF] Harwood | Assessing achievement goals in sport: Caveats for consultants and a case for contextualization[END_REF][START_REF] Murayama | The competition-performance relation: A meta-analytic review and test of the opposing processes model of competition and performance[END_REF]van de Pol et al., 2012avan de Pol et al., , 2012b;;van de Pol & Kavussanu, 2011, 2012), but instead that the type of goal endorsement depends on how competence is defined in a given competition, namely in an interpersonal (as in the match-play competition) or in an intrapersonal standard-based competition (as in the handicap competition).

Notwithstanding this contribution to the motivational dynamics at play in the sports domain, some limits of the present research should be noted. First, as the studies were on-line experiments, possible biases could not be excluded in comparison with fields experiments [START_REF] Gosling | Should we trust web-based studies? A comparative analysis of six preconceptions about internet questionnaires[END_REF]. Replicating the present results in a field experiment, possibly with an additional outcome (e.g., performance) may be an interesting prolongation of this work. Second, these results are very specific to the amateur golf domain. Future studies may examine the generalizability of the present findings to other sports in which competence can also be defined through an intrapersonal standard in competition. Finally, it should be noted that effect sizes are quite low in the two experiments (between .02 and .08). Thus, these effects must be interpret and discussed with caution.

Despite the need for further research to extend the present findings, these results make a contribution to the current knowledge on the competition-achievement goals relationship, as it shows that all forms of competition do not automatically result in other-approach goal endorsement. Thus, as suggested by several authors [START_REF] Harwood | Assessing achievement goals in sport: Caveats for consultants and a case for contextualization[END_REF]van de Pol et al., 2012b), if there is value in distinguishing contexts (i.e., training versus competition) when achievement goals are studied, paying attention on how competence is defined in a given competition (i.e., with interpersonal vs. intrapersonal standard) can also be particularly relevant.

Although our focus was on the approach dimension of achievement goals, as previously done in the sports domain [START_REF] Harwood | Assessing achievement goals in sport: Caveats for consultants and a case for contextualization[END_REF]van de Pol et al., 2012avan de Pol et al., , 2012b;;van de Pol & Kavussanu, 2011, 2012) and, hence providing a background for specific hypothesis testing, we also assessed the avoidance dimension of achievement goals. Confirming the rather exploratory nature of the competition avoidance achievement goal relation in sports, results for self-avoidance goal endorsement were somewhat inconsistent across the two studies. Indeed, whereas Experiment 1 showed that the competition condition, compared with the no-competition condition, led players to marginally endorse more selfavoidance goals, results from experiment 2 did not confirm these findings. Results for other-avoidance goal

  ,278) = 3.58, p = .029, indicating that participants in the interpersonal competition condition were younger (M = 54.90, SD = 11.42) than participants in the control condition (M = 59.34, SD = 10.53). Nevertheless, including participants' age in the analyses did not change the results. Participants in the no-competition condition read the same instructions as in Experiment 1. Participants in the handicap competition condition read the following: "The following sentences refer to the different kinds of goals that you might pursue when you play a competition for your handicap. Please indicate to what extent each statement is true for you during such a competition.". Participants in the match-play competition condition read the following: "The following sentences refer to the different kinds of goals that you might pursue when you play a match-play competition. Please indicate to what extent each statement is true for you during such a competition.". Participants subsequently answered the achievement goals questionnaire and provided demographic information.

This paper has been published in the International Journal of Sport Psychology in

This is the post-print version. The full reference is available at the end of the manuscript.

Acknowledgments

This work was supported by the Conseil Régional Auvergne, the French University Institute and the Swiss National Science Foundation. We also would like to acknowledge Mickaël Berthon and Julien Guegan from the CATECH (http://lapsco.univ-bpclermont.fr/catech/) technical support.

Competing with oneself or with others: Achievement goal endorsement in amateur golf competition 1

Mickaël Jury 1 , Annique Smeding 2 , Céline Darnon 1,3


Jean-François Pineau
email: jean-francois.pineau@ens-lyon.fr

Yves Robert
email: yves.robert@ens-lyon.fr

Frédéric Vivien
email: frederic.vivien@ens-lyon.fr

O-line and on-line scheduling on heterogeneous master-slave platforms

Keywords: scheduling, master-slave platforms, heterogeneous computing, on-line, release dates

In this paper, we deal with the problem of scheduling independent tasks on heterogeneous master-slave platforms. We target both o-line and on-line problems, with several objective functions (makespan, maximum response time, total completion time). On the theoretical side, our results are two-fold: (i) For oline scheduling, we prove several optimality results for problems with release dates; (ii) For on-line scheduling, we establish lower bounds on the competitive ratio of any deterministic algorithm. On the practical side, we have implemented several heuristics, some classical and some new ones derived in this paper, on a small but fully heterogeneous MPI platform. Our results show the superiority of those heuristics which fully take into account the relative capacity of the communication links.

Introduction

In this paper, we deal with the problem of scheduling independent tasks on a heterogeneous master-slave platform. We assume that this platform is operated under the one-port model, where the master can communicate with a single slave at any time-step. This model is much more realistic than the standard model from the literature, where the number of simultaneous messages involving a processor is not bounded. However, very few complexity results are known for this model (see Section 7 for a short survey). The major objective of this paper is to assess the diculty of o-line and on-line scheduling problems under the one-port model.

We deal with problems where all tasks have the same size. Otherwise, even the simple problem of scheduling with two identical slaves, without paying any cost for the communications from the master, is NP-hard [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF].

Assume that the platform is composed of a master and m slaves P 1 , P 2 , . . . , P m . Let c j be the time needed by the master to send a task to P j , and let p j be the time needed by P j to execute a task. Our main results are the following:

• When the platform is fully homogeneous (c j = c and p j = p for all j), we design an algorithm which is optimal for the on-line problem and for three dierent objective functions (makespan, maximum response time, total completion time)

• When the communications are homogeneous (c j = c for all j, but dierent values of p j ), we design an optimal makespan minimization algorithm for the o-line problem with release dates. This algorithm generalizes, and provides a new proof of, a result of Simons [START_REF] Simons | Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines[END_REF].

• When the computations are homogeneous (p j = p for all j, but dierent value of c j ), we failed to derive an optimal makespan minimization algorithm for the o-line problem with release dates, but we provide an ecient heuristic for this problem

• For these last two scenarios (homogeneous communications and homogeneous computations), we show that there does not exist any optimal on-line algorithm. This holds true for the previous three objective functions (makespan, maximum delay, total completion time). We even establish lower bounds on the competitive ratio of any deterministic algorithm.

The main contributions of this paper are mostly theoretical. However, on the practical side, we have implemented several heuristics, some classical and some new ones derived in this paper, on a small but fully heterogeneous MPI platform. Our (preliminary) results

show the superiority of those heuristics which fully take into account the relative capacity of the communication links.

The rest of the paper is organized as follows.

In Section 2, we state some notations for the scheduling problems under consideration. Section 3 deals with fully homogeneous platforms. We study communication-homogeneous platforms in Section 4, and computation-homogeneous platforms in Section 5. We provide an experimental comparison of several scheduling heuristics in Section 6. Section 7 is devoted to an overview of related work.

Finally, we state some concluding remarks in Section 8.

Due to lack of space, several proofs are omitted. See the extended version [START_REF] Pineau | O-line and on-line scheduling on heterogeneous master-slave platforms[END_REF] for further details.

Framework

To be consistent with the literature [START_REF] Lenstra | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF][START_REF] Blazewicz | Scheduling subject to resource constraints[END_REF], we use the notation α | β | γ where:

α: the platform As in the standard, we use P for platforms with identical processors, and Q for platforms with dierent-speed processors. We add M S to this eld to indicate that we work with masterslave platforms.

β: the constraints We write on-line for online problems, and r j when there are release dates. We write c j = c for communicationhomogeneous platforms, and p j = p for computation-homogeneous platforms.

γ: the objective We let C i denote the end of the execution of task i. We deal with three objective functions:

• the makespan (total execution time) max C i ;

• the maximum response time (or maxi-

mum ow) max C i -r i : indeed, C i -r i
is the time spent by task i in the system;

• the total completion time C i , which is equivalent to the sum of the response times

(C i -r i ).

Fully homogeneous platforms

For fully homogeneous platforms, we are able to prove the optimality of the Round-Robin algorithm which processes the tasks in the order of their arrival, and which assigns them in a cyclic fashion to processors:

Theorem 1. The Round-Robin algorithm is optimal for the problem P, M S | online, r j , p j = p, c j = c | (C i -r i ), as well as for the makespan and the maximum response time.

The proof is available in [START_REF] Pineau | O-line and on-line scheduling on heterogeneous master-slave platforms[END_REF]. First we show that the greedy algorithm (that assigns a new task to the rst idle processor) is optimal, and then we show that the Round-Robin algorithm starts tasks at the same time-steps as the greedy algorithm. We point out that the complexity of the Round-Robin algorithm is linear in the number of tasks and does not depend upon the platform size.

Communication-homogeneous platforms

In this section, we have c j = c but dierent-speed processors. We order them so that P 1 is the fastest processor (p 1 is the smallest computing time p i ), while P m is the slowest processor.

On-line scheduling

Theorem 2. There is no scheduling algorithm for the problem Q, M S | online, r i , p j , c j = c | max C i with a competitive ratio less than 5+3 √ 5 10 .

Proof. Suppose the existence of an on-line algorithm

A with a competitive ratio ρ = 5+3 √ 5 10 -, with > 0. We will build a platform and study the behavior of A opposed to our adversary. The platform consists of two processors, where p 1 = 2, p 2 = 1+3 √ 5 2

, and c = 1. Initially, the adversary sends a single task i at time 0. A sends the task i either on P 1 , achieving a makespan at least equal to 3, or on P 2 , with a makespan at least equal to 3+3 √ 5 2

. At time-step 1, we check if A made a decision concerning the scheduling of i, and the adversary reacts consequently:

1. If A did not begin the sending of the task i, the adversary does not send other tasks. The best makespan is then 4. As the optimal scheduling is 3, we have a competitive ratio of 4 3 > 5+3 √ 5 10 . This re- futes the assumption on ρ. Thus the algorithm A must have scheduled the task i at time 1.

If

A scheduled the task i on P 2 the adversary does not send other tasks. The best makespan is then

equal to 3+3 √ 5 2
, which is even worse than the previous case. Consequently, the algorithm A does not have another choice than to schedule the task i on P 1 .

At time-step 1, the adversary sends another task, j. In this case, we look, at time-step 2, at the assignment A made for j:

1. If j is sent on P 2 , the adversary does not send any more task. The makespan is then

5+3 √ 5 2
, whereas optimal scheduling is 5. The competitive ratio is then 5+3 √ 5 10 > ρ.

2. If j is sent on P 1 the adversary sends a last task at time-step 2. Best makespan is then 7+3

√ 5 2 , whereas the optimal is 5+3 √ 5 2
. The competitive ratio is still

5+3 √ 5
10 , higher than ρ.

Remark 1. Similarly, we can show that there is no on-line scheduling for the problem

Q, M S | online, r i , p j , c j = c | C i whose com- petitive ratio ρ is strictly lower than 2+4 √ 2 7
, and that there is no on-line scheduling for the prob-

lem Q, M S | online, r i , p j , c j = c | max (C i -r i )
whose competitive ratio ρ is strictly lower than 7 6 .

O-line scheduling

In this section, we aim at designing an optimal algorithm for the o-line version of the problem, with release dates. We target the objective max C i . Intuitively, to minimize the completion date of the last task, it is necessary to allocate this task to the fastest processor (which will nish it the most rapidly). However, the other tasks should also be assigned so that this fastest processor will be available as soon as possible for the last task. We dene the greedy algorithm SLJF (Scheduling Last Jobs First) as follows:

Initialization Take the last task which arrives in the system and allocate it to the fastest processor ( The second step is the most dicult.

For the rst step, we have to minimize the makespan during the scheduling of identical tasks with heterogeneous processors, without release dates. Without communication costs, this is a well-known load balancing, problem, which can be solved by a greedy algorithm [START_REF] Beaumont | The masterslave paradigm with heterogeneous processors[END_REF].

The scheduling backwards phase of SLJF solves this load balancing problem optimally. Since the problem is without release dates, the assignment phase does not increase the makespan, which thus remains optimal.

Next we add the constraints of release dates. To show that SLJF is optimal, we proceed by induction on the number of tasks. For a single task, it is obvious that the addition of a release date does not change anything about the optimality of the solution. Let us suppose the algorithm optimal for n tasks, or less. Then look at the behavior of the algorithm to process n + 1 tasks. If the addition of the release dates does not increase the makespan compared to that obtained during the memorization step, then an optimal scheduling is obtained. If not, let us look once again at the problem starting from the end. Compare the completion times of the tasks in the scheduling of the memorization phase (denoted as (C n -C i ) memo ), and in the assignment phase (denoted as (C n -C i ) nal ). If both makespans are equal, we are done. Otherwise, there are be the last task satisfying this property. In this case, the scheduling of the (n -j -1) last tasks corresponds to SLJF in the case of (n -j -1) tasks, when the rst task arrives at time r j+1 (see Figure 2). And since j is the last task satisfying the above property, we are sure that the processors are free at the expected times.

tasks such that (C n -C i ) memo < (C n -C i ) nal . Let j k → P2 Cl -Ck = 0 j → P3 Cl -Cj = 0 i → P1 Cl -Ci = 2 l → P1 Cl -Cl = 0
Scheduling is thus optimal from r j , and task j cannot begin its computation earlier. The whole scheduling is also optimal. Finally, SLJF is optimal to minimize the makespan in the presence of release dates.

Taking communications into account is now easy.

Under the one-port model, with a uniform communication time for all tasks and processors, the optimal policy of the master consists in sending the tasks as soon as they arrive. Now, we can consider the dates at which the tasks are available on a slave, and consider them as release dates for a problem without communications.

Remark 2. It should be stressed that, by posing c = 0, our approach allows to provide a new proof to the result of Barbara Simons [START_REF] Simons | Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines[END_REF].

Computation-homogeneous platforms

In this section, we have p j = p but processor links with dierent capacities. We order them, so that P 1 is the fastest communicating processor (c 1 is the smallest computing time c i ).

On-line scheduling

Just as in Section 4, we can bound the competitive ratio of any deterministic algorithm (but the proof is much more technical, see [START_REF] Pineau | O-line and on-line scheduling on heterogeneous master-slave platforms[END_REF]): Theorem 4. There is no scheduling algorithm for the problem P, M S | online, r i , p j = p, c j | max C i whose competitive ratio ρ is strictly lower than 6 5 .

O-line scheduling

In the easy case where m i=1 c i ≤ p, and without release dates, Round-Robin is optimal for makespan minimization. But in the general case, not all slaves will be enrolled in the computation. Intuitively, the idea is to use the fastest m links, where m is computed so that the time p to execute a task lies between the time necessary to send a task on each of the fastest m -1 links and the time necessary to send a task on each of the fastest m links. Formally,

m -1 i=1 c i < p ≤ m i=1 c i
With only m links selected in the platform, we aim at deriving an algorithm similar to Round-Robin. But we did not succeed in proving the optimality of our approach. Hence the algorithm below should rather be seen as a heuristic.

The diculty lies in deciding when to use the m -th processor. In addition to be the one having the slowest communication link, its use can cause a moment of inactivity on another processor, since m -1 i=2 c i +c m ≥ p.

Our greedy algorithm will simply compare the performances of two strategies, the one sending tasks only on the m -1 rst processors, and the other using the m -th processor at the best possible moment.

Let RRA be the algorithm sending the tasks to the m -1 fastest processors in a cyclic way, starting with the fastest processor, and scheduling the tasks in the reverse order, from the last one to the rst one. Let RRB be the algorithm sending the last task to processor m , then following the RRA policy. We see that RRA seeks to continuously use the processors, even though idle time may occur on the communication link, and on the processor P m . On the contrary, RRB tries to continuously use the communication link, despite leaving some processors idle.

The global behavior of the greedy algorithm,

SLJFWC (Scheduling the Last Job First With Communication) is as follows:

Initialization: Allocate the m -1 last tasks to the fastest m -1 processors, from the fastest to the slowest.

Comparison: Compare the schedules RRA and RRB. If there are not enough tasks to enforce the following stop and save condition, then keep the fastest policy (see Figure 3). (k ≥ 2), if (see Figure 4)

P2 : c = 2 P1 : c = 1 p = 8 m -2 X i=1 ci k m -1 X i=1 ci + cn (k + 1) m -1 X i=1 ci + cm m -2 X i=1 ci ... ... 1 2 3 4 5 6 7 1 2 3 4 ... ... j0 -3 j0 -2 j0 -1 j0 j0 j0 -1 j0-2 j0 -3 j0 -4
k m -1 i=1 c i + c m + m -2 i=1 c i > kp + m -2 i=1 c i (k + 1) m -1 i=1 c i + c m ≤ (k + 1)p
then keep the task assignment of RRB for the last k(m -1) + 1 tasks, and start again the comparison phase for the remaining tasks. If not, proceed with the comparison step.

End: When the last task is treated, keep the fastest policy.

The intuition under this algorithm is simple. We know that if we only have the m -1 fastest processors, then RRA is optimal to minimize the makespan. However, the time necessary for sending a task on each of the m -1 processors is lower than p. This means that the sending of the tasks takes advances compared to their execution. This advance, which accumulates for all the m -1 tasks, can become suciently large to allow the sending of a task on another m-th processor, for free, i.e. without delaying the treatment of the next tasks to come on the other processors.

MPI experiments

The experimental platform

We build a small heterogeneous master-slave platform with ve dierent computers, connected to each other by a fast Ethernet switch (100 Mbit/s). The ve machines are all dierent, both in terms of CPU speed and in the amount of available memory. The heterogeneity of the communication links is mainly due to the dierences between the network cards. Each task will be a matrix, and each slave will have to calculate the determinant of the matrices that it will receive. Whenever needed, we play with matrix sizes so as to achieve more heterogeneity in the CPU speeds or communication bandwidths.

Below we report experiments for the following conguration:

• c 1 = 0.011423 s, and p 1 = 0.052190 s

• c 2 = 0.012052 s, and p 2 = 0.019685 s

• c 3 = 0.016808 s, and p 3 = 0.101777 s

• c 4 = 0.043482 s, and p 4 = 0.288397 s.

Results

Figure 5 shows the makespan obtained with classical scheduling algorithms, such as SRPT (Shortest Remaining Procesing Time), List Scheduling, and several variants of Round-Robin, as well as with SLJF and SLJF W C. Each point on the gure, representing the makespan of a scheduling, corresponds in reality to an average obtained while launching several times the experiment.

We see that SLJF W C obtains good results. SLJF remains competitive, even if it was not designed for a platform with dierent communications links. Finally, Figure 7 represents the average makespan in the presence of release-dates. Again, SLJF W C performs well, even though it was not designed for problems with release-dates.

Related work

We classify several related papers along the following four main lines:

Models for heterogeneous platforms In the literature, one-port models come in two variants. In the unidirectional variant, a processor cannot be involved in more than one communication at a given time-step, either a send or a receive. In the bidirectional model, a processor can send and receive in parallel, but at most to a given neighbor in each direction. In both variants, if P u sends a message to P v , both P u and P v are blocked throughout the communication.

The bidirectional one-port model is used by Bhat et al [START_REF] Bhat | Ecient collective communication in distributed heterogeneous systems[END_REF][START_REF] Bhat | Ecient collective communication in distributed heterogeneous systems[END_REF] [START_REF] Khuller | On broadcasting in heterogenous networks[END_REF]. In this simpler model, the communication time only depends on the sender, not on the receiver: in other words, the communication speed from a processor to all its neighbors is the same.

Finally, we note that some papers [START_REF] Banikazemi | Communication modeling of heterogeneous networks of workstations for performance characterization of collective operations[END_REF][START_REF] Bar-Noy | Message multicasting in heterogeneous networks[END_REF] depart from the one-port model as they allow a sending processor to initiate another communication while a previous one is still on-going on the network.

However, such models insist that there is an overhead time to pay before being engaged in another operation, so there are not allowing for fully simultaneous communications.

Task graph scheduling Task graph scheduling is usually studied using the so-called macro-dataow model [START_REF] Norman | Models of machines and computation for mapping in multicomputers[END_REF][START_REF] Shirazi | Scheduling and load balancing in parallel and distributed systems[END_REF][START_REF] Chrétienne | Scheduling Theory and its Applications[END_REF][START_REF] El-Rewini | Task scheduling in multiprocessing systems[END_REF], whose major aw is that communication resources are not limited. In this model, a processor can send (or receive) any number of messages in parallel, hence an unlimited number of communication ports is assumed (this explains the name macro-dataow for the model).

Also, the number of messages that can simultaneously circulate between processors is not bounded, hence an unlimited number of communications can simultaneously occur on a given link. In other words, the communication network is assumed to be contention-free, which of course is not realistic as soon as the processor number exceeds a few units. More recent papers [START_REF] Tan | Minimizing the aplication execution time through scheduling of subtasks and communication trac in a heterogeneous computing system[END_REF][START_REF] Orduna | A new task mapping technique for communication-aware scheduling strategies[END_REF][START_REF] Roig | Improving static scheduling using intertask concurrency measures[END_REF][START_REF] Beaumont | A realistic model and an ecient heuristic for scheduling with heterogeneous processors[END_REF][START_REF] Beaumont | A polynomial-time algorithm for allocating independent tasks on heterogeneous fork-graphs[END_REF][START_REF] Sinnen | Communication contention in task scheduling[END_REF] take communication resources into account.

Hollermann et al. [START_REF] Hollermann | Scheduling problems in a practical allocation model[END_REF] and Hsu et al. On-line scheduling A good survey of on-line scheduling can be found in [START_REF] Sgall | On line scheduling-a survey[END_REF][START_REF] Pruhs | On-line scheduling[END_REF]. Two papers focus on the problem of on-line scheduling for master-slaves platforms. In [START_REF] Leung | Minimizing total completion time in master-slave systems[END_REF], Leung and Zhao proposed several competitive algorithms minimizing the total completion time on a master-slave platform, with or without pre-and post-processing. In [START_REF] Leung | Minimizing mean owtime and makespan on master-slave systems[END_REF], the same authors studied the complexity of minimizing the makespan or the total response time, and proposed some heuristics. However, none of these works take into consideration communication costs.

Conclusion

In this paper, we have dealt with the problem of scheduling independent, same-size tasks on masterslave platforms. We enforce the one-port model, and

we study the impact of the communications on the design and analysis of the proposed algorithms.

On the theoretical side, we have derived several new results, either for on-line scheduling, or for oline scheduling with release dates. There are two important directions for future work. First, the bounds on the competitive ratio that we have established for on-line scheduling on communication-homogeneous, and computation-homogeneous platforms, are lower bounds: it would be very interesting to see whether these bounds can be met, and to design the corresponding approximation algorithms. Second, there remains to derive an optimal algorithm for o-line scheduling with release dates on computation-homogeneous platforms.

On the practical side, we have to widen the scope of the MPI experiments. A detailed comparison of all the heuristics that we have implemented needs to be conducted on signicantly larger platforms (with several tens of slaves). Such a comparison would, we believe, further demonstrate the superiority of those heuristics which fully take into account the relative capacity of the communication links.

2 P 2 : p = 4 P 2 : p = 3 ( 1 : p = 2 P 2 : p = 4 P 2 : p = 3 ( 1 : p = 2 P 2 : p = 3 P 3 : 1 (Figure 1 .

 224231224231223311 Figure 1. Dierent steps of the SLJF algorithm, with four tasks i, j, k, and l.

jP1 : p = 2 P2 : p = 3 P3P1 : p = 2 P2 : p = 4 P2

 2324 Cl -Ci > 2 Cl -Cj > 0 Cl -Ck = 0 Cl -Cl = 0

Figure 2 .

 2 Figure 2. Detailing the last two phases of the SLJF algorithm.

8 P2 : c = 2 P1 : c = 1 P3 : c = 4 P4P4 : c = 5 P3 : c = 4 P2 : c = 2 p = 8 P1Figure 3 .P3 : c = 4 P4 : c = 5

 82145428345 Figure 3. Algorithms RRA and RRB with 9 tasks.

Figure 4 .

 4 Figure 4. The stop and save condition.

Figure 5 .

 5 Figure 5. Comparing the makespan of several algorithms.

Figure 7 .

 7 Figure 7. Makespan with release dates.

Figure 6

 6 Figure 6 also represents the average makespan of various algorithms, but on a dierent platform. This time, the parameters were modied by software in order to render the processors homogeneous. In this case, SLJF W C is still better, and SLJF obtains poor performances.

  [START_REF] Hsu | Task allocation on a network of processors[END_REF] introduce the following model for task graph scheduling: each processor can either send or receive a message at a given time-step (bidirectional communication is not possible); also, there is a xed latency between the initiation of the communication by the sender and the beginning of the reception by the receiver. Still, the model is rather close to the one-port model discussed in this paper.