Jean-Daniel Bontemps
email: jean-daniel.bontemps@engref.agroparistech.fr

Jan Esper
email: j.esper@geo.uni-mainz.de

Statistical modelling and RCS detrending methods provide similar estimates of long-term trend in radial growth of common beech in north-eastern France

Keywords: growth trends, dendrochronology, standardisation, statistical modelling, Fagus sylvatica

Dendrochronological methods have greatly contributed to the documentation of past long-term trends in forest growth. These methods primarily focus on the high-frequency signals of tree ring chronologies. They require the removal of the ageing trend in tree growth, known as "standardisation" or "detrending", as a prerequisite to the estimation of such trends. Because the approach is sequential, it may however absorb part of the low-frequency historical signal.

In this study, we investigate the effect of a sequential and a simultaneous estimation of the ageing trend on the chronology of growth. We formerly developed a method to estimate historical changes in growth, including a careful control of site fertility in the sampling design and a simultaneous separation of the site fertility, developmental stage, and calendar year effects on growth, using a statistical modelling (SM) approach. The method has been applied to the radial growth of dominant trees in even-aged stands of common beech in north-eastern France. We compare the SM method to the regional curve standardisation (RCS) method, which is widely used in dendrochronology, and has been proven to retain more long-term signals than other detrending techniques. We also test a variant of the RCS in which the developmental stage is measured by size rather than age, as is the case in the SM approach.

The SM and RCS methods produce similar long-term chronologies, showing an increase of approximately 50% in radial growth over the 20th century and a recent decline of around 18% in magnitude. The negative bias induced by the sequential estimation of ageing and date effects on growth in the RCS is identified, but remains minor. The chronology estimated by using the RCS variant (regional size curve) is lower in magnitude than that estimated by using the RCS, but the difference is moderate (5%).

These results highlight the conservative properties of the RCS with regard to the low-frequency historical signals in growth. They also suggest that singularly high estimates of growth trends reported in the dendrochronology literature are not method-dependent. We hypothesize that they may be caused by a negative site-age linkage in sampling designs. The decline reported for common beech in this temperate area of France is lower in magnitude than that evidenced in Mediterranean contexts.

Introduction

Since the discovery of long-term trends in forest growth [START_REF] Lamarche | Increasing atmospheric carbon dioxide: tree ring evidence for growth enhancement in natural vegetation[END_REF], the dendrochronological approach has been a main contributor to research on this topic in temperate/boreal ecosystems (Spiecker et al., 1996;[START_REF] Jacoby | Tree rings, carbon dioxide, and climatic change[END_REF][START_REF] Esper | Low-frequency signals in long tree-ring chronologies for reconstructing past temperature variability[END_REF][START_REF] Boisvenue | Impacts of climate change on natural forest productivityevidence since the middle of the 20th century[END_REF]. However, the nature of the signal extraction procedures used [START_REF] Briffa | Tree ring variables as proxy-climate indicators: problems with low-frequency signals[END_REF] has questioned the reliability of radial growth chronologies.

The traditional aim of dendrochronological methods is to build annual tree-ring chronologies, either for climate reconstruction purposes in dendroclimatology or for dating and analysing disturbances and variations in the local environment in dendroecology [START_REF] Fritts | Dendroclimatology and dendroecology[END_REF][START_REF] Fritts | Dendroecology: a tool for evaluating variations in past and present forest environments[END_REF].

Because high-frequency fluctuations are of primary interest, ring chronologies must be filtered out from the negative effect of ageing [START_REF] Fritts | Tree rings and climate[END_REF]. With increasing concern about the impact of global change on forest ecosystems, growing attention has been paid to low-frequency historical trends arising in chronologies [START_REF] Jacoby | Tree rings, carbon dioxide, and climatic change[END_REF][START_REF] Boisvenue | Impacts of climate change on natural forest productivityevidence since the middle of the 20th century[END_REF]. The dendrochronological approach has thus been applied as a method to separate ageing and historical trends in tree growth [START_REF] Becker | Long-term changes in forest productivity in northeastern France: the dendrocological approach[END_REF]Spiecker et al., 1996;[START_REF] Jacoby | Tree rings, carbon dioxide, and climatic change[END_REF]. While statistical methods are relevant for addressing confounding of factors, dendrochronological methods sequentially estimate the effects of age and date on growth. The effect of age is first estimated and then removed from ring size in a "detrending" or "standardisation" phase (Cook and Kairiukstis, 1990). In such a sequential procedure, the estimation of the age effect can absorb part of the lowfrequency historical trend recorded in tree rings, and reduce its magnitude in the final chronologies.

When these trends are positive (as most often encountered to date; [START_REF] Boisvenue | Impacts of climate change on natural forest productivityevidence since the middle of the 20th century[END_REF] the negative ageing trend will be estimated at a magnitude lower than it is in reality, and will result in a potential negative bias in these historical trends [START_REF] Fritts | Tree rings and climate[END_REF][START_REF] Briffa | Tree ring variables as proxy-climate indicators: problems with low-frequency signals[END_REF][START_REF] Briffa | A closer look at Regional Curve Standardization of tree-ring records: justification of the need, a warning of some pitfalls, and suggested improvements in its Application[END_REF]. Among other methods, the regional curve standardisation (RCS) method [START_REF] Becker | The role of climate on present and past vitality of silver fir forests in the Vosges mountains of northeastern France[END_REF][START_REF] Briffa | Fennoscandian summers from AD 500temperature changes on short and long time scales[END_REF] is known to retain more long-term trends than tree-level standardisation techniques [START_REF] Fritts | Tree rings and climate[END_REF] and has been intensively used to detect growth changes [START_REF] Boisvenue | Impacts of climate change on natural forest productivityevidence since the middle of the 20th century[END_REF]. The implementation of simultaneous signal separation methods such as the analysis of variance has been suggested [START_REF] Dupouey | A new method of standardization for examining long term trends in tree-ring chronologies[END_REF], but this method applies at a low resolution (age and date classes are required) and has been scarcely used [START_REF] Bergès | Long-term changes in wood density and radial growth of Quercus petraea Liebl. in northern France since the middle of the nineteenth century[END_REF]. The magnitude of the potential bias due to sequential estimation of age and historical trends in dendrochronological methods thus remains unknown.

We have previously addressed the issue of changes in forest growth through a modelling case study on even-aged stands of common beech (Fagus sylvatica L.) in north-eastern France [START_REF] Bontemps | Long-term changes in forest productivity: a consistent assessment in even-aged stands[END_REF]2010). Measuring historical growth variations in that species is of particular interest because common beech has been shown to experience recent climate-driven decline in both Mediterranean [START_REF] Jump | Rapid climate change-related growth decline at the southern range edge of Fagus sylvatica[END_REF][START_REF] Piovesan | Drought-driven growth reduction in old beech (Fagus sylvatica L.) forests of the central Apenines, Italy[END_REF]) and temperate [START_REF] Charru | Recent changes in forest productivity: An analysis of national forest inventory data for common beech (Fagus sylvatica L.) in northeastern France[END_REF] contexts, following decades of increases [START_REF] Badeau | Long-term growth trends of Fagus sylvatica L. in north-eastern France. A comparison between high and low density stands[END_REF][START_REF] Bontemps | Long-term changes in forest productivity: a consistent assessment in even-aged stands[END_REF]. How severe is this decline, relative to previous periods, and to what extend is the decline method-dependent are crucial issues. In our study, we applied the paired-plots sampling method [START_REF] Untheim | Has site productivity changed? A case study in the eastern Swabian Alb, Germany[END_REF] to accurately separate the effects of date and ageing on growth and control site fertility. It is based on the comparison of growth in pairs of young/old stands located at the same sites. The effects of site, developmental stage and calendar year were simultaneously estimated using a statistical modelling (SM) approach. For the dynamic interpretation of trends, the developmental stage was represented by size [START_REF] Bontemps | Long-term changes in forest productivity: a consistent assessment in even-aged stands[END_REF]. The radial growth of dominant trees at breast height revealed a 50% increase in growth rate over the 20th century [START_REF] Bontemps | Dominant radial and height growth reveal comparable historical variations for common beech in north-eastern France[END_REF]. Because the sampling was specifically designed to separate ageing and historical trends and the estimation method minimizes confounding problems, this chronology was considered to be a reliable baseline.

The first objective of the analysis was to study the impact of a sequential extraction of the effects of ageing and date on the final tree-ring chronology and on the magnitude of its variations, by applying the RCS detrending method. Because the SM and RCS methods also differ in the proxy used for the developmental stagesize or agea second objective was to assess the impact of an age/size substitution in the standardisation phase of the RCS. We thus applied a variant of the method where the developmental stage is represented by size.

Materials

We sampled pure and even-aged stands of common beech (Fagus sylvatica L.) in north-eastern France (semi-continental range). These stands are attested to have been managed as high forests since their origin [START_REF] Hüffel | Methods of forest planning in France[END_REF]. They were sampled in State forests to grant management continuity through time. Thinning operations in these forests are acknowledged to have been traditionally moderate [START_REF] Polge | The influence of thinnings on the growth constraints of Beech (in French)[END_REF].

The sampling relied on 14 pairs of young/old neighbouring stands [START_REF] Untheim | Has site productivity changed? A case study in the eastern Swabian Alb, Germany[END_REF][START_REF] Lebourgeois | Height and radial growth trends of Corsican pine in western France[END_REF] chosen for granting comparable site fertility conditions across generations. The procedure included control of topography, parent rock, soil texture and stoniness, and humus forms. The site conditions were further assessed from the measurement of environmental indicators, based on belowground vegetation and soil analyses (pH, cation exchange capacity, C:N ratio, phosphorus content, and soil water capacity or SWC). The average within-pair distance was 160 m. The older stand generation was on average 140.1 years old (SD: 20.2 yrs). The younger one was on average 64.6 year old (SD: 15.0 yrs). Systematic between-generation differences in environmental indicators were screened using paired t-tests. They confirmed the accuracy of the sample [START_REF] Bontemps | Long-term changes in forest productivity: a consistent assessment in even-aged stands[END_REF]. Details regarding the location, age, and site conditions of the sampled stands are listed in Dominant trees were defined as the 100 largest-diameter trees at a height of 1.30 m per hectare.

Accordingly, three dominant trees per stand were sampled in 0.06-ha circular plots, following the [START_REF] Duplat | Modelling of dominant height growth of sessile oak (Quercus petraea Liebl) in France. Regional variability and effect of the recent period (1959-1993)[END_REF] protocol. Tree-ring measurements were taken on stem disks sampled at a height of 1.30 m. On each disk, measurements of ring widths were performed to the nearest 1/100 mm using a digital positiometer and were repeated along four orthogonal radii distributed from a random primer direction. Ring series were cross-dated after the identification of pointer years. The mean of the four ring width series available for each tree was first computed. As the purpose was the analysis of the radial growth of dominant trees, a raw mean growth chronology was computed for each stand, providing an estimate of the annual growth rate in dominant radius (corresponding to the dominant ring width, or RW 0 ). In total, 2379 annual increments arising from the 28 stands were available. The tree-ring series are shown against cambial age, size, and calendar year in

Methods

Statistical modelling approach (SM)

The model was elaborated and fitted in [START_REF] Bontemps | Dominant radial and height growth reveal comparable historical variations for common beech in north-eastern France[END_REF].

Model structure and functional expression

The dominant radius and ring width were denoted by R 0 and RW 0 respectively. The radial growth rate of the dominant trees was written as a multiplicative composition of the developmental stage, site and date effects. It was basically modelled by a growth equation (f 1 ) accounting for the effect of developmental stage represented by size R 0 , and the effect of site represented by a single parameter S. This parameter was identified with the multiplicative scale parameter of the equation. The effect of calendar year was expressed as a function f 2 of time measured from a base date (t b ) and introduced in the model as a multiplier of the site parameter (a particular value S b of S is observed at date t b ). The radial growth rate was approximated as the annual ring width. The model is expressed as follows:

RW 0 (t) = f 2 (t -t b ) S b f 1 (R 0 (t -1)) (1)
where f 2 (t b ) = 1.

Because the radial growth series exhibited a maximum followed by a decreasing but nonasymptotic pattern (Figure 1), we represented the effect of developmental stage by a nonasymptotic sigmoid growth curve. The corresponding growth equation was parameterised to identify the vertical scale parameter as the maximum growth rate (S b ) and the horizontal scale parameter as the radius of the maximum growth rate (K). Its expression is as follows:

RW 0 = S b f 1 (R 0 ) = S b (R 0 / K) m / (1 -m + m (R 0 / K)) with m < 1 (2)
where S b is the maximal growth rate (mm/yr), K is the radius (mm) at which S b is observed, and m is a shape parameter (dimensionless).

The effect of calendar year (f 2 ) was represented by a cubic spline function with equally spaced nodes using a 15-yr internode and with t b = 1900. The vector of the spline parameters was denoted by 

Figure 1a

Statistical methodology

The data are longitudinal and are organized according to two nested levels corresponding to stand pairs and stands within pairs (hereafter denoted by levels 1 and 2). Accordingly, the models were fitted using hierarchical non-linear mixed-effects models [START_REF] Lindström | Nonlinear mixed effect models for repeated measures data[END_REF] fitted by maximum likelihood. S b was found to vary between stand pairs (level 1). K was found to vary at level 2, with a systematically lower value for the younger generation. The residual variance was modelled as a power function of the expected increment. The statistical expression of the model is given in Eq. ( 3):

RW 0 (t) = f 2 (t -t b , ) S b f 1 (R 0 (t -1), K, m) +  t (3) with: S b ~ N(Sb 0 ,  Sb,1 ), K ~ N(K 0 ,  K,2 ),  t ~ N(0, V( t )), V( t ) =  2 0 Ŵ R (t) 2
where  is the power for the residual variance function, S b and K are considered random parameters with Gaussian distribution, and  Sb,1 and  K,2 are their standard deviations. S b0 , K 0 , m, ,  Sb,1 ,  K,2 ,  and  are fixed parameters. The model parameter estimates are listed in Table 2 of Bontemps et al. (2010).

Regional curve standardisation approach (RCS)

Principle

The RCS technique [START_REF] Erlandsson | Dendrochronological studies[END_REF] is described in [START_REF] Becker | The role of climate on present and past vitality of silver fir forests in the Vosges mountains of northeastern France[END_REF] and has been named as RCS since [START_REF] Briffa | Fennoscandian summers from AD 500temperature changes on short and long time scales[END_REF]. The basic principle of standardisation techniques is to remove age-related signals in growth series to obtain a bias-free chronology (Cook and Kairiukstis, 1990).

Standardisation is achieved by dividing the size of each available ring by the value expected from its cambial age in a reference curve. Such a curve can be estimated either by fitting smoother functions to individual growth series against cambial age oras is the case in the RCSby averaging all individual series of a sample according to cambial age and smoothing this mean curve. This curve is typically deemed the "regional curve" (RC). Because rings averaged at each cambial age refer to different dates, the RC usually shows strong regularity [START_REF] Becker | The role of climate on present and past vitality of silver fir forests in the Vosges mountains of northeastern France[END_REF][START_REF] Esper | Low-frequency signals in long tree-ring chronologies for reconstructing past temperature variability[END_REF]. The RCS method has been reported to retain more low-frequency signals than methods based on individual-tree detrending [START_REF] Becker | The role of climate on present and past vitality of silver fir forests in the Vosges mountains of northeastern France[END_REF][START_REF] Briffa | Fennoscandian summers from AD 500temperature changes on short and long time scales[END_REF][START_REF] Esper | Low-frequency signals in long tree-ring chronologies for reconstructing past temperature variability[END_REF][START_REF] Melvin | A "signal-free" approach to dendroclimatic standardisation[END_REF].

Computations and chronology estimation

The RCS methodology was applied to the dominant radial growth series. For each ring, the cambial age i is denoted by a i with a i  [1, a max ], where a max is the maximum cambial age over the dataset.

The calendar year j is denoted by t j with t j  [t min , t max ], the year range of the dataset. The number of rings available at age a i and date t j is denoted by n ij . Ring widths at age a i and year t j are denoted by RW 0 (a i , t j ) and are further indexed by k  [1, n ij ] when n ij > 1.

The RC was calculated for all a i as:

           max min max min t t t t n , n t , a RW a RW j ij j 1 k j i k 0 i 0 ij (5)
The RC was smoothed (denoted by 0 RW ) using a polynomial function fitted by ordinary least squares. A polynomial of degree 4 was selected from successive F-tests for nested model comparison [START_REF] Seber | Linear Regression Analysis[END_REF]. Each ring RW 0 (a i , t j ) was then standardised to a growth index I 0 (a i , t j ) using Eq. ( 6):

) ( ) , ( ) , ( i 0 j i 0 j i 0 a RW t a RW t a I  (6)
The RCS chronology was finally obtained by averaging growth indexes at each calendar year t j :

           max max a i a n n t a I t I 1 ij 1 i j i 1 k k 0, age j 0 , ij (7)

Variant based on regional size curve

All the notations are the same except for R 0 , which varies in [R 0min , R 0max ] (minimum and maximum dominant radius over the sample). Because the dominant radius is a continuous variable, the RC was directly estimated from a polynomial fit of ring widths against dominant radii ( 0 RW (R 0 )).

Based on the same nested model comparison procedure, a polynomial of degree 4 was selected and ring widths were detrended using:

      0 0 j 0 0 j 0 0 , , R RW t R RW t R I  (8)
The regional chronology was calculated as the average of growth indexes at each calendar year:

           max min max min R R i R R n n t R I t I 0 0 0 0 ij ij i j i 0 1 k k 0, size j 0 , (9)
To facilitate the comparison between the different methods, the annually resolved RCS chronologies were smoothed using a local cubic spline. Finally, to express the evolution in growth relative to the same reference year (taken as 1900) as in the modelling approach, the RCS chronologies were adjusted to the 1900 level of the applied cubic-spline smoothers.

In the following section, all reported trends and their differences are thus measured on a relative scale with the value 1 in 1900 and are equivalently expressed in percentages of variation since that date.

Results

RCS chronology estimate

The RCS chronology estimate is shown in Figure 2. A progressive increase in radial growth rate is evident. The first peak is observed in the 1920s at a level of +25%. The maximum level of increase was a rise of 49% in the mid 1980s, relative to 1900. The period 1950-1990 is reported to be very favourable to radial growth. The average increase over the 20th century is 26.0%. The long-term trend reveals medium-term variations including reductions in the 1940s and 1990s, where it reduces to a level of +13% and +32%, respectively. These periods include singular successions of years showing low levels of growth. The RCS chronology also confirms the large amplitude of interannual growth variations. Some years reveal especially strong negative deviations (the most severe being 1921, 1947-49, 1964, and 1976).

RCS variant based on regional size curve and comparison with the RCS

The RCS variant chronology is shown in Figure 2. The annual and medium-term variations depicted in this chronology are identical to those of the standard RCS. The maximum level of growth is again recorded in the mid 1980s at a level of 44%, close to that depicted in the standard RCS. However, the RCS variant is found to produce a systematically lower estimate of the longterm trend across calendar years. The difference is greatest around the peaks of the increases in the 1920s (-7%) and in the 1960-1980s (-6%) and reaches a minimum -2.8% in the 1950s. Over the 20th century, the average increase is 4.4% below the standard RCS estimate (+21.6%).

Figure 2. Comparison of radial growth chronologies estimated by the RCS method and the RCS variant (based on a regional size curve).

Both chronologies were smoothed using a cubic spline smoother. Full lines: RCS chronology based on the regional size curve, dotted lines: RCS chronology based on the regional age curve.

Comparison of SM and RCS chronology estimates

The comparison of SM and standard RCS chronologies is shown in Figure 3. The SM and RCS chronologies were very similar, in both the course and amplitude of past variations. The difference in the 20th century average trend is below 2% (+24.7% for the SM chronology). At their maximum level in the 1980s, the difference is only 3% (SM: +47%, RCS: 49%). The greatest difference is observed in the 1970s when the standard RCS trend denotes a less marked growth reduction during that decade. The order relationship between the two chronologies swaps between the first and second halves of the century (level of +25% for the peak in the 1920s in the SM approach), indicating a slightly higher mean trend in the RCS chronology.

The comparison between the RCS variant and SM chronologies (Figure 3) reveals similar patterns, with a closer fit than between the standard RCS and SM records. However, the RCS variant chronology falls noticeably below the SM record in the first half of the century, with values up to -12% in the 1920s. The average growth trend over the 20th century is 3% below that of the SM chronology.

Figure 3. Comparison of radial growth chronologies estimated by the RCS (Regional Curve standardisation) and SM (Statistical Modelling) methods.

Full black line: RCS chronology based on the regional age curve. Dotted black line: SM chronology. Full grey line: RCS variant chronology based on the regional size curve. The RCS chronologies were standardised according to the smoother estimates of 1900, for comparison with the SM chronology.

Discussion

RCS detrending has been applied for the analysis of long-term trends in forest growth. The estimation of trend magnitude leans on specific working assumptions of the method: (i) The estimation of the developmental stage and calendar year effects on growth is sequential and not simultaneous as in a statistical approach. (ii) The developmental stage is measured by the cambial age of the rings and not by tree size. When growth is affected by a long-term trend, trees of a given age show different sizes in time. Tree size may therefore be more accurate than age for measuring the developmental stage. We tested the following hypotheses related to these assumptions: (i) The prior removal of developmental stage may absorb part of the long-term trend. This hypothesis was tested by a comparison with a statistical model applied to the same sample, where ageing and historical effects are estimated simultaneously. (ii) The trend is influenced by the proxy used for measuring the tree developmental stage (age or size). This hypothesis was tested by implementing a variant of the RCS method where the developmental stage is substituted by size. This variant was also required to compare the RCS and SM approaches on the basis of a unique proxy for the ageing trend.

Effect of developmental stage proxy: comparison of standard RCS and RCS variant

The standard RCS and RCS variant chronologies displayed very similar variations through the 20th century. The RCS variant also produced a systematically lower trend (Figure 2). The magnitude of the difference varied between 3 and 7% (mean for RCS trend: +26.0%, for RCS variant: +21.6%).

Our interpretation of the difference is as follows. An increase in growth implies that larger tree sizes are attained within a given period of time. When growth increments are expressed as a function of size, growth-size curves of the young trees are thus expanded to the right, relative to those of the older trees. This expansion effect does not occur when increments are expressed as a function of age (see Figures 1a and1b). Because the increments increase with developmental stage in the younger tree generation (Figure 1), the expansion effect brings the growth-size curves of the two tree generations closer than in a comparison at a constant age. The growth trend estimate is thus of lower magnitude when standardisation is based on the sizerather than the agecurve. A mathematical interpretation of this age/size substitution effect is provided in the Appendix.

In our view, there are two reasons why the use of size instead of age for measuring developmental stage should be preferred. First, a number of papers have demonstrated a direct size-dependence of metabolic processes associated with tree growth [START_REF] Shinozaki | A quantitative analysis of plant form -the pipe model theory. I Basic analyses[END_REF][START_REF] Valentine | Tree-growth models: derivations employing the pipe-model theory[END_REF][START_REF] Ryan | Age-related decline in forest productivity: pattern and process[END_REF][START_REF] West | A general model for ontogenetic growth[END_REF], whereas there is poor evidence of true ageing processes in tree species [START_REF] Thomas | Ageing in plants[END_REF]. Second, the growth trend can be interpreted as a contraction of the time period required to reach a given dimension when growth is compared at constant size [START_REF] Bontemps | Long-term changes in forest productivity: a consistent assessment in even-aged stands[END_REF], which is crucial for forest planning. This is not true for a comparison at a constant age associated with sizes that differ in time.

Effect of sequential estimation: comparison of RCS variant and SM methods

Because the size-for-age substitution impacts the trend retained in the RCS approaches, we discuss the comparison of the RCS variant and the SM chronologies. The prior removal of developmental stage was hypothesised to capture some of the long-term trend [START_REF] Fritts | Tree rings and climate[END_REF]. Our results (Figure 3) suggest that this hypothesis is only partially true for this current sampling. The RCS variant chronology falls below the SM chronology over the first half of the study period, but the records become closer over the following period and culminate at a similar level. Over the century, the mean trend of the RCS variant is 3.1% below the SM mean trend (+21.6%/+24.7%). The present study shows that the sequential extraction of the effects negatively impacts the magnitude of trend, but the effect remains moderate. Very similar decennial variations in growth rate are also depicted in the two methods.

The first interpretation of this finding is related to the structure of the retrospective sampling designs. The regional curve is calculated as an average over all trees, both young and old individuals. Therefore, when a positive trend affects tree-rings, the regional curve is overestimated in the older trees and underestimated in the younger ones. In retrospective sampling designs, the proportion of old tree rings increases when moving back in time. In contrast, the recent period is equally covered by young and old tree rings. While growth indexes might be underestimated for remote periods, biases in the estimate of the size effect may somehow compensate over generations for a recent period. The definition of this "recent period" depends on the age range covered by the younger available trees. The second interpretation lies in the uniqueness of the regional curve in the RCS. The RC estimation requires a matching of all tree-ring series by age (or size), resulting in a chronological misalignment of rings (Cook and Kairiukstis, 1990). As soon as the sampled trees offer a significant range of ages (or sizes), decennial variations in the growth rate (Figure 2) cannot be captured by the RC average. This conservative property of the RCS method with regard to the historical signal does not hold true in tree-based standardisation methods [START_REF] Fritts | Tree rings and climate[END_REF]. However, it requires that a wide range of tree ages be sampled.

Statistical modelling or RCS method: which method to use?

The RCS method is a filtering method used to estimate growth chronologies [START_REF] Fritts | Dendroclimatology and dendroecology[END_REF] and it is not intended for the study of ageing processes in growth. The statistical modelling (SM) method is aimed at describing and quantifying growth patterns [START_REF] Pretzsch | Models for forest ecosystem management: A European perspective[END_REF] and it has been extended to perform the estimation of long-term trends [START_REF] Elfving | Trends of tree growth in Swedish forests 1953-1992: an analysis based on sample trees from the National Forest Inventory[END_REF]. Because both methods are used for such estimations, the question arises as to which one to choose.

First, the RCS methodology is a heuristic method of estimation, not a method based on a fitting criterion. It consists of a sequential non-parametric estimate of the effects of age and calendar year. To avoid possible biases in the chronologies due to this sequential procedure, a "signal-free" RCS methodology has recently been proposed [START_REF] Melvin | A "signal-free" approach to dendroclimatic standardisation[END_REF]. This relies on an iterative estimation of the age curve and the growth index chronology. However, the simultaneous separation of factors, based on a fitting criterion, is precisely the aim of statistical methods (the maximum likelihood or least squares criteria require the solving of a system of simultaneous equations in the model parameters). It allows an estimation of the trend conditional on other effects, i.e. "other things being equal". Second, the statistical approach requires the formulation of a model.

Assumptions relative to the expression and articulation of the different effects are explicit. The interpretation of the trend can thus be discussed with respect to the model expression, which is more ambiguous in the RCS approach. As an illustration, the effects of size and date in the SM approach (Eq. ( 1)) are clearly assumed to be multiplicative. Eqs. ( 8) and ( 9) in the RCS method suggest that the combination of these effects is not far from being multiplicative, but how far remains unknown.

Finally, no inference in a statistical sense is made possible when applying the RCS. In our modelling approach [START_REF] Bontemps | Dominant radial and height growth reveal comparable historical variations for common beech in north-eastern France[END_REF], statistical inference made it possible in particular, to decide which growth equation best described the ageing effect, to identify a significant divergence between young and old trees at a recent period, and to derive a confidence interval for the long-term trend, based on the properties of parameter estimators. However, the SM approach implementation is less straightforward, and is of limited interest for fast exploratory analyses.

We sampled stands of restricted ages, managed as even-aged high forests since their origin, with moderate interventions [START_REF] Polge | The influence of thinnings on the growth constraints of Beech (in French)[END_REF]. Accordingly, the observed ageing trends in growth chronologies were found to be regular and fairly homogenous over the sample (Figure 1). They did not challenge the estimation of the regional age curve (RCS) and required reasonable assumptions in the modelling approach [START_REF] Bontemps | Dominant radial and height growth reveal comparable historical variations for common beech in north-eastern France[END_REF]. In more natural old-growth forest ecosystems, disturbances and episodes of stand closure result in release/suppression phases in rings of surviving trees [START_REF] Devall | Dendroecological analysis of a Fitzroya cupressoides and a Nothofagus nitida stand in the Cordillera Pelada, Chile[END_REF][START_REF] Di Filippo | Bioclimatology of beech (Fagus sylvatica L.) in the Eastern Alps: spatial and altitudinal climatic signals identified through a tree-ring network[END_REF]. The RCS originally foresees the combining of data from a larger number of trees in which presumed disturbance events do not occur synchronously.

Here again, the averaging process greatly attenuates the impact of isolated disturbances (Cook and Kairiukstis, 1990). The regional curve may, however, remain uncertain in the late-growth domain, as replication of very old trees is often low [START_REF] Briffa | A closer look at Regional Curve Standardization of tree-ring records: justification of the need, a warning of some pitfalls, and suggested improvements in its Application[END_REF]. The modelling approach can be extended to any set of growth chronologies as long as some common ageing pattern can be identified and can be accurately described by a mathematical function (f 1 in Eq. 1 can be replaced by any appropriate function). The minimum assumption of a decreasing ageing trend remains plausible even in old-growth forest trees facing disturbances (Fritts, 1976, chapter 6;[START_REF] Devall | Dendroecological analysis of a Fitzroya cupressoides and a Nothofagus nitida stand in the Cordillera Pelada, Chile[END_REF]. Other general models that capture successions of suppression-release phases in tree-ring chronologies have also been formulated [START_REF] Warren | On removing the growth trend from dendrochronological data[END_REF].

Role of sampling designs in growth trend studies

Our results show that there is no major impact of the signal extraction method used (RCS or SM) on the magnitude of the trend. In addition, the reported trend shows an increase of around 50%, which is half as much as reported in [START_REF] Badeau | Long-term growth trends of Fagus sylvatica L. in north-eastern France. A comparison between high and low density stands[END_REF] applying the RCS to data from the same species, forest structure and area (increase >100% over 1900-1990). In the dendroecology literature, recurrent high (and sometimes seemingly excessive) estimates for long-term trends have been reported. For example, a 100% increase over the 20th century was found in [START_REF] Lamarche | Increasing atmospheric carbon dioxide: tree ring evidence for growth enhancement in natural vegetation[END_REF], [START_REF] Schadauer | Growth trends in Austria[END_REF], [START_REF] Rathgeber | Productivity increase of pubescent oak in the French Mediterranean area (in French)[END_REF][START_REF] Vejpustkova | Growth trends of spruce in the Orlické hory Mts[END_REF], while increases up to 200-300% have also been reported [START_REF] Becker | Long-term changes in forest productivity in northeastern France: the dendrocological approach[END_REF]. Our comparison suggests that no bias in the RCS is likely to amplify the reported trend. Our estimate was obtained from a sampling design intended to carefully balance site and age dimensions. In addition, studies on permanent plot designs [START_REF] Eriksson | Yields of Norway spruce (Picea abies (L.) Karst.) in two consecutive rotations in southwestern Sweden[END_REF][START_REF] Elfving | Trends of tree growth in Swedish forests 1953-1992: an analysis based on sample trees from the National Forest Inventory[END_REF][START_REF] Dhôte | Productivity changes in four sessile oak forests since 1930: a standlevel approach (in French)[END_REF] and dendrochronology studies including a careful control of site conditions [START_REF] Szeicz | Growth trends and climatic sensitivity of trees in the North Patagonian rain forest of Chile[END_REF][START_REF] Bergès | Long-term changes in wood density and radial growth of Quercus petraea Liebl. in northern France since the middle of the nineteenth century[END_REF][START_REF] Podlaski | Radial growth trends of fir (Abies alba Mill.), beech (Fagus sylvatica L.), and pine (Pinus sylvestris L.) in the Swietokrzyski National Park (Poland)[END_REF] have reported trends that are around 40-50% in magnitude. We therefore hypothesize that some of the reported estimates may result from imbalances in sampling designs.

Sampling campaigns oriented towards growth trend analysis require that a wide range of tree ages be considered and that age and site fertility be balanced [START_REF] Spiecker | Growth trends in European forests -do we have sufficient knowledge?[END_REF]. However, the control of site conditions is explicit in only a few of the aforementioned studies (prior age/site balance in the sampling in [START_REF] Szeicz | Growth trends and climatic sensitivity of trees in the North Patagonian rain forest of Chile[END_REF][START_REF] Podlaski | Radial growth trends of fir (Abies alba Mill.), beech (Fagus sylvatica L.), and pine (Pinus sylvestris L.) in the Swietokrzyski National Park (Poland)[END_REF] or posterior control of designs in [START_REF] Bergès | Long-term changes in wood density and radial growth of Quercus petraea Liebl. in northern France since the middle of the nineteenth century[END_REF]. Rather, a recurrent and pragmatic approach relies on building wide samples over a regional or national forest resource [START_REF] Hornbeck | Growth trends in 10 species of trees in New England, 1950-1980[END_REF][START_REF] Schadauer | Growth trends in Austria[END_REF][START_REF] Becker | Long-term changes in forest productivity in northeastern France: the dendrocological approach[END_REF], in which age classes and site conditions are assumed to balance. In managed forests, however, the older stands are often located in less fertile conditions, where harvesting is postponed [START_REF] Badeau | Long-term growth trends of Fagus sylvatica L. in north-eastern France. A comparison between high and low density stands[END_REF][START_REF] Becker | Long-term changes in forest productivity in northeastern France: the dendrocological approach[END_REF][START_REF] Piovesan | Drought-driven growth reduction in old beech (Fagus sylvatica L.) forests of the central Apenines, Italy[END_REF], resulting in a possibly positive artifact in the magnitude of growth trends. This site-age linkage may even be valid in natural forests, as evidence for a growth rate-longevity trade-off has also been reported (Penuelas, 2005). The sampling design-hypothesis has been poorly addressed. Using a dendrochronological approach, [START_REF] Bert | Vitalité actuelle et passée du sapin (Abies alba Mill) dans le Jura. Etude dendroécologique[END_REF] sampled several hundred trees to cover the regional variability in site conditions of silver fir in the Jura Mountains. Interestingly, they showed that 50% of the initial trend was removed when a posterior stratification of site fertility was applied [START_REF] Becker | Long-term changes in forest productivity in northeastern France: the dendrocological approach[END_REF].

Prior control of age-site balance in sampling designs remains crucial when the purpose is to diagnose growth trends, in the field of dendroecology. The paired-plots sampling, as applied here, offers a way to control the balance of these factors. When plots are sampled without a specific control of site conditions, the collection of environmental information related to these plots is fundamental for posterior resampling.

Conclusion

It was shown that: (i) the sequential estimate of the regional curve (RC) and the historical chronology in the RCS method has a negative impact on the long-term trend retained in detrended chronologies; (ii) the use of age instead of size as a proxy for developmental stage in the RC computation increases the magnitude of the retained trend. Because these effects are opposed, the similarity between the standard RCS and the statistical modelling (SM) chronologies was partially inflated. Nevertheless, these effects are quantitatively moderate, and the chronologies developed with the RCS or the SM methods are found to be in good agreement. Our results point toward the conservative nature of the RCS with respect to low-frequency historical signals in growth. Also, while the RCS method is easier to implement, the SM approach provides a more interpretable signal and should be preferred in the specific context of the assessment of growth trends. Regional curves based on cambial age or tree size were equally easy to implement, and size may constitute a better proxy for developmental stage when tree growth is affected by a long-term trend.

As an outcome of this comparative study, we hypothesize that high trend estimates from some previous dendrochronological studies are related to a negative age-site bias in the sampling designs.

Therefore, the careful control and presentation of these sampling designs remains a crucial need in such studies. The decline in the growth of common beech has been observed since 1985, and it reaches a magnitude of -35% (RCS) and -40% (SM) relative to that date. The end-20th century level of growth is close to that of the 1960s. This decline is therefore less acute than that evident in Mediterranean contexts [START_REF] Jump | Rapid climate change-related growth decline at the southern range edge of Fagus sylvatica[END_REF][START_REF] Piovesan | Drought-driven growth reduction in old beech (Fagus sylvatica L.) forests of the central Apenines, Italy[END_REF].

And because F 1 = f 1 o f R -1 : R = f 0 (S) * f 1 (a 0 + ) * f 2 ' (date) (A.12)

The comparison of f 2 and f 2 ' (Eq. (A.3) and (A.12)) depends on the variations of f 1 with age (ageing effect on growth).

3. Comparison of age-and size-related historical trends f 2 and f 2 '

Usually, f 1 is a function with a maximum, increasing at early developmental stage and decreasing over the remainder of the tree lifespan. Because the decreasing phase is not observed in the younger tree generation of our sample (Figure 1), the comparison of growth is established over stages where f 1 is predominantly an increasing function of age. Thus we have:

f 1 (age + ) > f 1 (age) (A.13)
By equating Eqs. (A.3) and (A.12) using (A.13), we deduce that:

f 2 ' < f 2

Conclusion

The estimate of growth trend based on a growth comparison at constant size is lower than that based on a comparison at constant age if the growth phase compared across tree generations in the sample exhibits a positive pattern with the developmental stage (as in the case of the present study). The contrary would be true if the growth phase compared decreases across the developmental stage. No immediate conclusion could be drawn if both increasing and decreasing phases were represented in the younger generation of trees sampled.

  Figure 1.

Figure 1c Figure 1 .

 1c1 Figure 1c

Table 1 . Stand pair Forest Location 1 Stand age 2 Site conditions Oldest

 1

		Youngest	Elevation	P 3	T 4	SWC 5	pH 6
	(yrs)	(yrs)	(m)	(mm)	(°C)	(mm)

Table 1 . Location, age and site conditions of the sampled common beech stands. 1

 1

	Mean

Appendix

Effect of proxy selected for tree developmental stage (size or age) on the magnitude of growth trend The radial growth increment R is considered to be dependent on the permanent site conditions (S), developmental stage, and calendar year. Stand density is omitted. The growth trend is estimated by comparing increments in trees of the same developmental stage, growing at different dates, which is achieved by removing the ageing trend in tree rings. We compare the magnitude of these trends when cambial age or size (R) is chosen as a proxy for the developmental stage.

Comparison of growth increments at a constant cambial age

When the environment is stationary, the increment is written:

where f 0 and f 1 are the effects of site and age. S is a constant indicating the site conditions. Here and in the following, "*" indicates a function composition that respects the sign of the function effects on R (for instance multiplicative in the formulation of Eq. ( 1)). We now consider a particular cambial age a 0 for the comparison:

When the environment is non-stationary and positive growth trends are induced, a function of calendar year f 2 is introduced in (A.2), corresponding to the modification of site conditions:

where f 2 is an increasing function of date.

Comparison of growth increments at a constant size

We consider the size-age relationship R = f R (age) that applies in a stationary environment. The specific size R 0 is reached at the cambial age a 0 :

The function f R is a strictly increasing function of age, and we may write:

In order to express growth as a function of size, Eq. (A.2) is thus rewritten as: -1 and simplify Eq. (A.6) as:

When the environment is non-stationary and positive growth trends are induced, a function of calendar year f 2 is introduced in Eqs. (A.6/A.7). As a main difference, the size-age relationship (A.4) is also affected by a positive shift ( f R ' > f R ) or say equivalently, a higher size R 0 ' is reached at the same age a 0 . Eq. (A.7) is thus rewritten as:

Because f R is a strictly increasing function of age, we may find  > 0 such that:

f R "(a 0 ) = f R (a 0 + ) (A.10) From Eqs. (A.8), (A.9) and (A.10), we thus have: .11)


Giorgio Lucarelli

Ioannis Milis
email: milis@aueb.gr

Vangelis Th Paschos
email: paschos@lamsade.dauphine.fr

On the max-weight edge coloring problem

Keywords: weighted edge coloring, polynomial algorithms, approximation algorithms

We study the following generalization of the classical edge coloring problem: Given a weighted graph, find a partition of its edges into matchings (colors), each one of weight equal to the maximum weight of its edges, so that the total weight of the partition is minimized. We explore the frontier between polynomial and NP-hard variants of the problem as well as the approximability of the NP-hard variants.

Introduction

In several communication systems messages are to be transmitted in a single hop from senders to receivers through direct connections established by an underlying switching network. In such a system, a sender (resp. receiver) cannot send (resp. receive) more than one messages at a time, while the transmission of messages between different senders and receivers can take place simultaneously. The scheduler of such a system establishes successive configurations of the switching network, each one routing a non-conflicting subset of the messages from senders to receivers. Given the transmission time of each message, the transmission time of each configuration equals to the heaviest message transmitted. Moreover, in practice there is a significant setup delay to establish each configuration. Note, for example, that in optical switches this overhead may dominate the transmission time. The aim of the scheduler is to find a sequence of configurations such that all the messages to be finally transmitted and the total transmission time (including setup delays) to be minimized. This problem can be formulated in graph-theoretic terms as following: senders and receivers can be considered as the vertices V of a weighted graph G = (V, E), whose edges E correspond to messages and their weights w(e), e ∈ E, to the lengths (transmission times) of messages. Although the graph G obtained is originally a weighted directed one, it can be considered as an undirected one, since the directions of its edges do not play any role in the objective function we study here. Clearly, a configuration corresponds to a matching or a color (in terms of edge coloring) of the graph G. In this context, we ask for a partition M = {M 1 , M 2 , . . . , M s } of E into matchings (colors), each one of weight w i = max{w(e)|e ∈ M i }, such that W = s i=1 w i is minimized. Due to the fact that the weight w i of each color is defined as the maximum weight of the edges colored i, in the following we shall refer to this problem as Max-weight Edge Coloring (MEC) problem.

Clearly, if all the edges of G are of the same weight then the MEC problem reduces to the classical edge coloring problem, where the objective is to minimize the number of colors (matchings) required in order to assign different colors to neighbor edges.

The MEC problem is equivalent to the parallel batch scheduling problem with incompatibilities between jobs. According to the standard notation for scheduling problems we denote this variant as 1 | pbatch, graph | C max . In this variant jobs are no more independent but they correspond to the edges of a weighted graph. Edge weights correspond to processing times of jobs and the graph G describes incompatibilities between jobs i.e., jobs corresponding to adjacent edges cannot be scheduled in the same batch (color).

In this paper we study the frontier between polynomial and NP-variants of the MEC problem as well as the approximability of its NP-hard variants. In the next section we review briefly the related work, while in Section 3 we give the notation we use and some preliminaries. As the complexity of the problem on trees remains open, in Section 4 we present a polynomial algorithm for trees of bounded degree and in Section 5 a polynomial algorithm for stars of chains. Finally in Section 6 we present an approximation for bipartite graphs which beats the known one for bipartite graphs of maximum degree ∆ ≤ 7.

Related work

It is known that the MEC problem is strongly NP-hard even for: (i) bipartite graphs of maximum degree three and edge weights restricted to be to 1, 2 or 3 [START_REF] Gopal | Minimizing the number of switchings in a SS/TDMA system[END_REF][START_REF] Kesselman | Non-preemptive scheduling of optical switches[END_REF], (ii) k-regular bipartite graphs for k ≥ 3 [START_REF] Demange | Weighted node coloring: when stable sets are expensive[END_REF], and (iii) cubic bipartite planar graphs [START_REF] De Werra | Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation[END_REF]. Yet another NP-hardness proof for an equivalent formulation of the MEC problem on bipartite graphs in terms of matrix decomposition has been proposed in [START_REF] Rendl | On the complexity of decomposing matrices arising in satellite communication[END_REF].

Demange et al. in [START_REF] Demange | Weighted node coloring: when stable sets are expensive[END_REF] have been also shown that the MEC problem on k-regular bipartite graphs cannot be approximated within a ratio less than 2 k 2 k -1 , which for k = 3 becomes 8/7. This inapproximability result has been improved, by the same authors in [START_REF] De Werra | Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation[END_REF], to 7/6 for bipartite cubic planar graphs.

On the other hand, a 2-approximation algorithm has been presented in [START_REF] Kesselman | Non-preemptive scheduling of optical switches[END_REF] for bipartite graphs. It is easy to see that the same algorithm applies also for general graphs. In addition, a 5/3-approximation algorithm for bipartite graphs of maximum degree ∆ = 3 has been presented in [START_REF] Demange | Weighted node coloring: when stable sets are expensive[END_REF]. In general, this algorithm gives an approximation ratio equal to 2∆-1 3 for bipartite graphs with ∆ ≥ 3. In [START_REF] De Werra | Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation[END_REF] has been presented a new algorithm for bipartite graphs of maximum degree ∆ = 3 that achieves an approximation ratio equal to the 7/6-inapproximability result.

A natural idea to decrease the cost of a solution to such a weighted edge coloring problem is to allow the division of each edge e of G into parallel edges of weights adding up to w(e). In fact, this idea corresponds to the notion of preemption in scheduling problems: interrupt the execution of a job (the transmission of a message) and complete it later. The weight of each color M i is now defined as w i = max{w i (e)|e ∈ M i }, where w i (e) is the portion of the e's weight belonging to matching M i , and we ask for a partition M such that s i=1 w i (e) = w(e), ∀e ∈ E, and W = s i=1 w i is minimized. We shall refer to this variant as preemptive MEC (p-MEC) problem.

The existence of a setup delay, d, encounter in practical applications to establish each matching (configuration), does not make any difference for the MEC problem: this can be taken into account by increasing the weight of all edges of G by d. Thus, the weight of each matching in M will be also increased be d, incorporating the set-up delay for this matching. On the contrary, the presence of such a parameter affects crucially the complexity of the p-MEC problem. In the absence of d the p-MEC problem is equivalent to the preemptive open shop scheduling problem which can be solved optimally in polynomial time [START_REF] Lawler | On preemptive scheduling of unrelated parallel processors by linear programming[END_REF]. However, in the presence of d the p-MEC problem becomes strongly NP-hard [START_REF] Gopal | Minimizing the number of switchings in a SS/TDMA system[END_REF] and non approximable within a factor less than 7/6 [START_REF] Crescenzi | On approximating a scheduling problem[END_REF]. Approximation algorithms of factors 2 and 2 -1 d+1 have been presented in [START_REF] Afrati | Scheduling in switching networks with set-up delays[END_REF] and [START_REF] Crescenzi | On approximating a scheduling problem[END_REF], respectively.

The analogous, to the MEC problem, Max-weight Vertex Coloring (MVC) problem has been studied more extensively in the literature during last years [START_REF] Brucker | Scheduling a batching machine[END_REF][START_REF] Finke | Batch processing with interval graph compatibilities between tasks[END_REF][START_REF] Demange | Weighted node coloring: when stable sets are expensive[END_REF][START_REF] De Werra | Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation[END_REF][START_REF] Escoffier | Weighted coloring: further complexity and approximability results[END_REF][START_REF] Pemmaraju | Buffer minimization using max-coloring[END_REF][START_REF] Pemmaraju | Approximation algorithms for the max-coloring problem[END_REF]. In the MVC problem we ask for a partition of the vertices of G into independent sets (colors), each one of weight equal to the maximum weight of its vertices, so that the total weight of the partition is minimized.

Note that the MEC problem, on a general graph G, is equivalent to the MVC problem on the line graph, L(G), of G and thus any algorithm for the MVC problem applies also to the MEC problem. However, this is not true for special graph classes, since the line graph of a special graph (e.g. bipartite or tree) is not anymore in the same special class.

Notation and Preliminaries

In the following we consider the MEC problem on a weighted graph G = (V, E). By d(v), v ∈ V , we denote the degree of vertex v and by ∆(G) (or simply ∆) the maximum vertex degree of G. We define the degree of each edge e(u, v) ∈ E as d(u, v) = d(u) + d(v) and ∆ ′ (G) (or simply ∆ ′ ) denotes the maximum edge degree.

It is well known that the classical edge coloring problem, is NP-hard even in cubic graphs [START_REF] Holyer | The NP-completeness of edge-coloring[END_REF], although its optimal solution is either ∆ or ∆ + 1 [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF]. On the other hand, it is solvable in polynomial time for bipartite graphs [START_REF] König | ber graphen und iher anwendung auf determinantentheorie und mengenlehre[END_REF]. Obviously, applying such an algorithm on a weighted bipartite graph we obtain a ∆-colors solution, in general non optimal, to the MEC problem. For the number of matchings in an optimal solution of the MEC problem the following bound holds.

Proposition 1 For the number of matchings, s * , in an optimal solution it holds that

∆ ≤ s * ≤ ∆ ′ -1 ≤ 2∆ -1.
Proof: Any solution consists of at least ∆ matchings, since there is a vertex with exactly ∆ adjacent edges which belong in different matchings.

Assume that an optimal solution consists of ∆ ′ or more matchings. Consider those matchings sorted in non-increasing order of their weights. Each edge of G has at most ∆ ′ -2 neighbor edges. So, for each edge e in any (∆ ′ + i)-th matching, i > 0, there is one of the first ∆ ′ -1 matchings where e can be moved without increasing the weight of this matching.

The last part of the inequality follows directly by the definition of ∆ ′ .

The MEC problem is also polynomial for graphs of maximum degree ∆ = 2. This result follows from the same variant of the MVC problem. In [START_REF] Escoffier | Weighted coloring: further complexity and approximability results[END_REF] has been presented an O(|V | 2 ) algorithm for the MVC problem on chains, which can be easily adapted for the MVC problem on graphs of maximum degree ∆ = 2 (collections of chains and cycles). Moreover, if G is a graph of maximum degree two, then its line graph L(G) is also a graph with ∆(L(G)) = 2 and the following theorem holds.

Theorem 1 An optimal solution to the MEC problem for graphs of maximum degree ∆ = 2 consists of at most three (i.e., two or three) matchings and can be found in O(|E| 2 ) time.

In the rest of this paper we consider the edges of G sorted in nonincreasing order of their weights, w(e 1 ) ≥ w(e 2 ) ≥ . . . ≥ w(e m ). Thus, e 1 denotes the heaviest edge of G.

By OP T we denote the cost of an optimal solution to the MEC problem. We also assume that in such an optimal solution the graph is decomposed into s * matchings each one of weight w * i . Without loss of generality we consider the matchings of any solution in non-increasing order of their weights, i.e. w 1 ≥ w 2 ≥ . . . ≥ w s , and for the optimal solution w * 1 ≥ w * 2 ≥ . . . ≥ w * s * .

Trees

In this section we first present a polynomial algorithm for a related decision problem called Feasible k-Coloring. This algorithm is then used to derive a polynomial algorithm for the MEC problem on trees of bounded degree. The Feasible k-Coloring problem is formally defined as following. An analogous problem is also defined and solved in [START_REF] Pemmaraju | Approximation algorithms for the max-coloring problem[END_REF] for the MVC problem on trees.

Feasible k-Coloring:

Instance: A tree T (V, E), a weight function w(e) : E → N and a sequence of k integer weights a 1 , a 2 , . . . , a k , such that a 1 ≥ a 2 ≥ . . . ≥ a k . Question: Is there a partition of the set of edges E into exactly k matchings M 1 , M 2 , . . . , M k , such that w j ≤ a j , 1 ≤ j ≤ k?

We consider the tree T rooted at an arbitrary vertex, r. For each edge e = (v, u) we define u to be the most distant from r endpoint of e, and T (e) to be the subtree of T rooted at u. We denote by S(e) ⊆ {M 1 , M 2 , . . . , M k } to be the set of matchings in which edge e can belong in order the subtree T (e) ∪ {e} to be feasibly colorable.

Our algorithm initializes the sets S(e) for each leaf edge e to contain the matchings that are heaviest than its weight w(e). Moreover, a fictive edge e 0 of weight w(e 0 ) = 0 is connected to the root of the tree, as in Figure 1.a, in order to treat the root of the tree as the rest vertices. The Feasible k-Coloring algorithm follows.

Algorithm 1 1. Initialization:

Leaf edges: S(e) = {M j |1 ≤ j ≤ k and w(e) ≤ a j } Rest edges: S(e) = {} Add a fictive vertex r ′ , a fictive edge e 0 = (r ′ , r) with w(e 0 ) = 0 and a fictive matching M 0 with w 0 = a 0 = 0 2. For each e ∈ E ∪ {e 0 } in post-order do 3. For each matching M j such that w(e) ≤ a j do 4.

If there is coloring of T (e) ∪ {e} such that e ∈ M j then 5.

S(e) = S(e) ∪ {M j } 6. If S(e) = ∅ then return 7. Create a feasible coloring using the S(e)'s

In line 4, Algorithm 1 decides if a feasible coloring for the subtree T (e) ∪ {e} exists (see Figure 1.b). For each edge e = (v, u), we define E u = {e u

1 , e u 2 , . . . , e u d } to be the set of edges from u to its children (recall that u is the most distant from the root of the tree endpoint of e). Each edge e u i can belong in one of the matchings in its S(e u i ). Let Q be the union of the sets S(e u i ), but the matching M j edge e is assigned to, i.e. Q = We create a bipartite graph B(E u , Q; S), where there is an edge between e u i ∈ E u and M q ∈ Q iff M q ∈ S(e u i ). Then we create a flow network F by joining a source vertex s to each vertex in E u and a terminal vertex t to each vertex in Q, as in Figure 1.c. We assign to all the edges in F a weight equal to 1. Then, it follows that there is coloring of T (e) ∪ {e} such that e ∈ M j iff there is in F an st flow of value d.

In line 7, Algorithm 1 creates a partition of the edges of T into matchings. This can be done by considering the edges of T in pre-order and assigning an edge e in an arbitrary matching in its set S(e).

Algorithm 1 performs k • |E| iterations and in each one of them runs a maximum flow algorithm of O(poly) time. Thus, the next Theorem follows.

Theorem 2 There a polynomial time algorithm for the Feasible k-Coloring problem.

Algorithm 1 can be used to solve the MEC problem on trees, as following.

Stars of chains

A star consists of m edges e 1 , e 2 , . . . , e m sharing a common endpoint. Obviously, the optimal solution to the MEC problem for such a weighted star is of cost OP T = m i=1 w(e i ) and consists of exactly ∆ = m matchings. A star of chains consists of p chains C 1 , C 2 , . . . , C p all starting from a common vertex, say u. We consider each chain C i , 1 ≤ i ≤ p, starting from u with an edge e u i which we call start edge. We also assume w.l.o.g. that w(e u 1 ) ≥ w(e u 2 ) ≥ . . . ≥ w(e u p ).

Lemma 1 For an optimal solution of the MEC problem on a star of chains the following hold: i) The number of matchings s * equals to either p or p + 1.

ii) Only k ≤ 3 matchings have cardinality

|M j | > 1.
iii) At least the k -1 heaviest start edges appear in these k matchings.

Proof: i) By Proposition 1, ∆ ≤ s * ≤ ∆ ′ -1.
Here, ∆ = p and ∆ ′ = p + 2.

ii) Assume that an optimal solution has more than three matchings of cardinality |M j | > 1. Consider those matchings sorted in non-increasing order of their weights. Each non start edge e has at most 2 neighbor edges. So, such an edge e can be moved in one of the three first heaviest matchings, since its neighbor edges can belong in at most two different matchings.

iii) Consider first that k = 2. Assume that in the optimal solution the heaviest start edge e u 1 does not belong to neither of two matchings of cardinality |M j | > 1. Then e u 1 can be either inserted in one of those two matchings (if this does not contain another start edge) or e u 1 can replace an existing start edge. In both cases the cost of the optimal solution decreases or remains the same.

Assume next that k = 3. As in the previous case e u 1 can be inserted in one of the three matchings of cardinality |M j | > 1. Similarly, e u 2 can be inserted in one of the rest two of those matchings.

In the following we distinguish between two cases according to possible number of matchings in an optimal solution, i.e. p + 1 or p.

If an optimal solution consists of p + 1 matchings then it contains exactly one matching without any start edge. Algorithm 3 finds such an optimal schedule with p + 1 matchings. The complexity of Algorithm 3 is dominated by line 2 and by Theorem 1 it is O(|E| 2 ).

If an optimal solution consists of p matchings, then each of them contains a start edge. Algorithm 4 returns such an optimal schedule with p matchings. Find the optimal solution S * (H) using Theorem 1 6.

Combine the solutions S * (T ) and S * (H) into exactly 3 matchings 7.

Find a solution for the initial star consisting of these 3 matchings plus p -3 matchings each one containing one of the removed p -3 start edges 8. Return the best solution found Algorithm 2 is used in line 3 since T is a bounded degree tree with ∆ = 3 and it returns an optimal solution S * (T ) of at least three matchings. In line 6, a 3-matchings optimal solution for the edges in T and H can be obtained by considering the matchings in both solutions in non-increasing order of their weights and merging the matchings of each solution having the same rank, since T and H are vertex-disjoint. The optimality of the solution that Algorithm 4 returns follows by Lemma 1 using the same arguments as for Algorithm 3.

The complexity of the algorithm is dominated by line 3 which takes O(|E| 3 ) time and is executed ∆ -2 times.

The optimal solution to the MEC problem on stars of chains is the best between the solution found by Algorithm 3 (optimal with p + 1 matchings) and the one found by Algorithm 4 (optimal with p matchings), since, according to Lemma 1, the optimal solution consists of either p + 1 or p matchings. Thus, the following theorem holds.

Theorem 4

The MEC problem on stars of chains can be solved optimally in O(∆ • |E| 3 ) time.

Bipartite graphs

In this section we present an algorithm, denoted by A(G), that improves the 2 approximation ratio given in [START_REF] Kesselman | Non-preemptive scheduling of optical switches[END_REF] for the MEC problem in bipartite graphs of maximum degree ∆ ≤ 7. The main idea of our algorithm is the following: for a given bipartite graph G, of maximum degree ∆, run ∆ -1 algorithms, A ∆ , A ∆+1 , . . . , A 2∆-1 , and select the best solution found. Each A ∆+k , 0 ≤ k ≤ ∆ -1, algorithm splits the graph G into two subgraphs G 1 and G 2 such that the graph G 1 contains heavy edges and has maximum degree ∆(G 1 ) ≤ k. Note that in general ∆(G 2 ) ≤ ∆(G). Given this splitting of G each algorithm A ∆+k returns a solution of cost W ∆+k , by concatenating the following solutions of the MEC problem on G 1 and G 2 : (i) for the graph G 2 the algorithm finds a ∆-matchings solution by solving the classical edge coloring problem on G 2 , (ii) for the graph G 1 the algorithm finds a solution of at most 2∆(G 1 ) -1 matchings using (recursively) algorithm A(G 1 ).

For k = 0, G 2 coincides with G and therefore algorithm A ∆ returns a ∆-matchings solution found as in point (i) above. For the weight of such a solution it holds that W ∆ ≤ ∆ • w * 1 , since for the weight, w i , of any matching of this solution it holds that w i ≤ w(e 1 ) = w * 1 . For k = 1, G 1 is a maximal matching of G created by examining its edges in non-increasing order of their weights. This matching is of weight w 1 = w(e 1 ). Algorithm A ∆+1 uses also algorithm A ∆ (G 2 ). The cost of the solution that algorithm A ∆+1 returns is W ∆+1 ≤ w * 1 + ∆ • w * 2 , since no edge e of weight w(e) > w * 2 belongs to G 2 (if such an edge belongs to G 2 , then it is not in M 1 because a heavier one of its adjacent edges is in M 1 , a contradiction).

In general, algorithm A ∆+k , k ≥ 2, repeatedly splits the graph G into graphs G 1 and G 2 , with G 1 containing edges heavier than a parameter c, taking as values the weights of the edges of the graph G. The algorithm returns the best of the solutions found in these iterations. If ∆(G 1 ) = 2 then find an optimal solution for the graph G 1 5.

Else run A(G 1 ) 6.

Use A ∆ for G 2 7. Return the best solution found

The case of k = 2 is treated in a different way than the cases of k ≥ 3, since in this case ∆(G 1 ) = 2, and an optimal solution for G 1 can be found by Theorem 1. Thus, for k = 2 we obtain

Lemma 2 Algorithm A ∆+2 returns a solution of cost W ∆+2 ≤ w * 1 + w * 2 + ∆ • w * 3 .
Proof: A ∆+2 returns the best solution found with weight W ∆+2 = min{w 1 + w 2 + w 3 + ∆ • w 4 } for different values of c = w 4 . Consider the cost of the solution found by the algorithm in the iteration for which w 4 = w * 3 . In this iteration the edges of G 1 are a subset of the edges in the two heaviest matchings of the optimal solution. Therefore for this iteration it holds that W ∆+2 ≤ w * 1 + w * 2 + ∆ • w * 3 , since ∆(G 1 ) = 2 and thus the optimal solution for G 1 can be found by Theorem 1.

Using algorithms A

∆ , A ∆+1 and A ∆+2 , algorithm A(G) returns a solu- tion of cost W = min{W ∆ , W ∆+1 , W ∆+2 }, that is W ≤ ∆ • w * 1 W ≤ w * 1 + ∆ • w * 2 W ≤ w * 1 + w * 2 + ∆ • w * 3
Multiplying these inequalities by z 1 , z 2 and z 3 , respectively, and adding them we obtain

W • (z 1 + z 2 + z 3 ) ≤ w * 1 • (z 1 • ∆ + z 2 + z 3 ) + w * 2 • (z 2 • ∆ + z 3 ) + w * 3 • (z 3 • ∆) W OP T ≤ t z 1 + z 2 + z 3 where t = z 1 •∆+z 2 +z 3 = z 2 •∆+z 3 = z 3 •∆.
Thus, the best approximation ratio is achieved when the quantity t z 1 +z 2 +z 3 is minimized. Therefore, we want to:

min t z 1 + z 2 + z 3 such that (z 1 • ∆ + z 2 + z 3 ) = t (z 2 • ∆ + z 3 ) = t (z 3 • ∆) = t z 1 , z 2 , z 3 ≥ 0
Solving this problem we obtain a new approximation ratio for the MEC problem in bipartite graphs with ∆ ≥ 3, which is:

W OP T ≤ ∆ 3 3∆ 2 -3∆ + 1 = ̺ ∆+2
This ratio is unbounded, but gives better results than the approximation ratio (2∆ -1)/3 given in [START_REF] Demange | Weighted node coloring: when stable sets are expensive[END_REF], for any ∆, as well as than the 2-approximation algorithm given in [START_REF] Kesselman | Non-preemptive scheduling of optical switches[END_REF], for ∆ = 3 and ∆ = 4. In fact, ̺ ∆+2 becomes 27/19 ≃ 1.42 for ∆ = 3 and 64/37 ≃ 1.73 for ∆ = 4. Note, however, that an 1.17-approximation algorithm is known [START_REF] De Werra | Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation[END_REF] for bipartite graphs with ∆ = 3.

The behavior of algorithm A(G) for bipartite graphs of ∆ ≥ 4, is improved if one allows the use of algorithms A ∆+3 , A ∆+4 and so on. In fact, for k = 3 we have:

Lemma 3 Algorithm A ∆+3 returns a solution of cost W ∆+3 ≤ ̺ ∆+2 • (w * 1 + w * 2 + w * 3 ) + ∆ • w * 4 .
Proof: Similarly to the proof of Lemma 2, in some iteration of algorithm A ∆+3 , the maximum edge in G 2 is equal to w * 4 and the edges of G 1 are a subset of the edges in the three heaviest matchings of the optimal solution. As ∆(G 1 ) = 3, the algorithm A(G 1 ) return a ̺ ∆+2 approximate solution for the graph G 1 .

Working as above we obtain that algorithm A(G), for bipartite graphs with ∆ ≥ 4, leads to an approximation ratio

̺ ∆+3 = 19∆ 4 76∆ 3 -138∆ 2 + 100∆ -27 .
This ratio improves the result for ∆ = 4, where the ratio becomes 1.61 from 1.73. Moreover, for ∆ = 5 this ratio becomes 1.82.

In general, the algorithm A(G) gives a better approximation ratio than 2 for bipartite graphs with ∆(G) ≤ 7. The following In general, the complexity of algorithm A(G) is dominated by the complexity of A 2∆(G)-1 , which calls recursively at most |E| times algorithm A(G 1 ), where ∆(G 1 ) ≤ ∆(G) -1. The recursion depth is at most ∆ -2, since the recursion stops in A ∆+2 . Each iteration of each A ∆+k algorithm, 0 ≤ k ≤ ∆ -1, calls algorithm A ∆ , which runs in polynomial time. Thus, algorithm A ∆ is called O(|E| ∆(G)-2 ) times, in total, by algorithm A(G).

Remark: Concerning general graphs, note that an edge coloring using (∆+ 1) matchings can be found in polynomial time. Thus, modifying algorithm A ∆ to find such a coloring of ∆+1 (instead of ∆) matchings, algorithm A(G) works also for general graphs. Furthermore, it beats the 2-approximation algorithm in [START_REF] Kesselman | Non-preemptive scheduling of optical switches[END_REF] for graphs of ∆ = 3 and ∆ = 4, achieving ratios 1.73 and 1.93, respectively.

Figure 1 :

 1 Figure 1: (a) The fictive edge e 0 . (b) An instance of the graph in line 4 of Algorithm 1. (c) The flow network constructed in line 4 of Algorithm 1. All edges have weight equal to 1.

Algorithm 2 1 .Theorem 3

 13 For k = ∆ to ∆ ′ -1 do 2. For all |E| k combinations of edge weights, such that w 1 ≥ w 2 ≥ . . . ≥ w k and w 1 = max{w(e)|e ∈ E}) do 3.Run Algorithm 1 4. Return the best of the solutions found Line 3 of Algorithm 2 is repeated O(∆ • |E| ∆ ) times, and therefore it is polynomial only for trees of polynomially bounded degree. There a polynomial time algorithm for the MEC problem in trees with polynomially bounded degree.

Algorithm 3 1 .

 1 Remove from the star the p -2 lightest start edges (this creates a graph H consisting of p -1 chains) 2. Find an optimal solution S * (H) for the graph H, using Theorem 1 3. If there are 3 non empty matchings in S * (H) then 4. Return the solution consisting of these 3 matchings of S * (H) plus p -2 matchings each one containing one of the removed p -2 lightest start edges Note that Algorithm 3 is possible to return p -1 matchings of |M i | = 1, in the case where the one of the three matchings of S * (H) found in line 2 consists of a single edge. Taking into account Lemma 1, it follows that Algorithm 3 returns the optimal solution of p + 1 matchings since: (i) the p -(k -1) matchings of cardinality |M i | = 1 contain the p -(k -1) lightest start edges (one per each matching) and (ii) the cost of k matchings is optimal.

Algorithm 4 1 .

 1 For i = 3 to p do 2. Remove p -3 start edges e u 3 , e u 4 , . . . , e u i-1 , e u i+1 , . . . , e u p (this creates a star T of 3 chains and a graph H of p -3 chains) 3. Find the optimal solution S * (T ) using Theorem 3 4. If there are exactly 3 matchings in S * (T ) then 5.

Algorithm 5 -

 5 A ∆+k 1. For each weight c = w(e 1 ), w(e 2 ), . . . do 2. Split G into edge induced subgraphs G 1 = {e|w(e) > c} and G 2 = {e|w(e) ≤ c} 3. If ∆(G 1 ) ≤ k then 4.

  table summarizes the best approximation ratio achieved by our algorithm and the previous best known ratio for different values of ∆.

	∆	3	4	5	6	7	8
	our ratio	1.42 1.61 1.75 1.86 1.95 2.03
	previous ratio 1.17	2	2	2	2	2

* Funded by the PENED 2003 Programme of the EU and the Greek General Secretariat for Research and Technology † Part of this work has been carried out while the author was visiting the Department of Informatics of Athens University of Economics and Business


Bernard Roy
email: roy@lamsade.dauphine.fr

Roman Słowiński
email: ro-man.slowinski@cs.put.poznan.pl

Handling effects of reinforced preference and counter-veto in credibility of outranking

Keywords: Decision support, Multiple criteria analysis, Outranking, Concordance, Discordance

The aim of this paper is to generalize the way of computing the credibility of outranking in a multiple criteria aggregation procedure, in view of taking into account two new effects called reinforced preference and counter-veto. These effects concern only those criteria for which, as soon as action a is "judged very strongly preferred" to action b, one wishes that the credibility of outranking of a over b is greater than that for the case where (all things equal elsewhere) the preference is not "judged very strong". To achieve this goal, we propose two complementary ways. The first one involves a reinforced preference threshold which affects the concordance degree, and the second one involves a counter-veto threshold which affects the insertion of discordance degree in the calculation of the credibility of outranking. The introduction of these two new effects remains compatible with the handling of purely ordinal preference scales. The resulting new index of the credibility of outranking can be used, in particular, in ELECTRE methods.

Prise en compte de préférences renforcées et contre veto dans la crédibilité d'un surclassement

Résumé L'objet de cet article est d'étendre le mode de calcul de la crédibilité d'un surclassement dans une procédure d'agrégation multicritère afin de pouvoir prendre en compte deux nouveaux effets appelés préférences renforcées et contre veto. Ces effets ne concernent que les critères à propos desquels, dès lors qu'une action a est « jugée très fortement préférée » à une action b, on souhaite que la crédibilité du surclassement de a vis-à-vis de b soit plus élevée que ce qu'elle serait (toutes choses égales par ailleurs) si la préférence n'était pas « jugée très forte ». Deux possibilités complémentaires sont proposées pour atteindre ce but. L'une repose sur l'introduction d'un seuil de préférence renforcée qui affecte le degré de concordance et l'autre sur celle d'un seuil de contre veto qui affecte le degré de discordance.

L'introduction de ces deux nouveaux effets reste compatible avec la prise en compte d'échelles de préférence purement ordinales. La nouvelle définition de l'indice de crédibilité du surclassement qui en résulte peut, en particulier, être substituée à l'ancienne dans les méthodes ELECTRE, sans apporter d'autres modifications.

Mots clés : Aide multicritère à la décision ; Surclassement ; Concordance ; Discordance.

Motivations

Suppose that a consistent family of criteria F={g 1 , g 2 , …, g n } has been build in view of comparing actions from a finite set A={a, b, c,…}. Each criterion g j , j=1,…,n, may be associated with indifference and/or preference thresholds, denoted as q j and p j , respectively [START_REF] Figueira | ELECTRE methods[END_REF][START_REF] Roy | Multicriteria Methodology for Decision Aiding[END_REF][START_REF] Roy | Paradigms and challenges[END_REF]. We assume, without loss of generality, that the preference increases with the performance level g j (a), a∈A. We are considering comparisons of actions which result in an outranking relation S for all ordered pairs of actions (a,b)∈A, such that aSb means "a is at least as good as b". The assertion aSb involves two concepts known as concordance and discordance. The outranking relation aSb is characterized by the credibility index σ(a,b) [START_REF] Figueira | ELECTRE methods[END_REF]. The way of calculating σ(a,b) will be reminded in Section 2.

The credibility index involves preference scales which are purely ordinal. For this reason, as soon as on criterion g j , the difference of performances g j (a) -g j (b) becomes greater than the preference threshold, the value of this difference does not influence the credibility of outranking of action a over action b. If one would judge that a very large value of this difference gets the meaning of "very strong preference", then one could wish to take this judgment into account in the definition of the credibility of outranking of a over b. To satisfy such a wish, we are proposing two complementary ways:

• the first one involves a new threshold called reinforced preference threshold: it corresponds to the value of the difference of performances g j (a) -g j (b) which is "judged meaningful" for considering criterion g j as more important in the concordant coalition (by increasing its weight), comparing to the situation where (all things equal elsewhere) the difference of performances is smaller than this threshold (however, not smaller than the preference threshold); • the second one involves another threshold called counter-veto threshold (it is not necessarily equal to the previous one, as it has a different meaning and it plays a different role): it corresponds to the value of the difference of performances g j (a) -g j (b) which is "judged meaningful" for weakening the mechanism of veto against the credibility of outranking (from the side of discordant criteria), comparing to the situation where (all things equal elsewhere) the difference of performances is smaller than this threshold (however, not smaller than the preference threshold).

These two ways are presented in Sections 3 and 4, respectively. In the last Section, we comment the possible use of the new credibility index, in particular, within ELECTRE methods.

Credibility of outranking -a brief reminder

Consider an ordered pair of actions (a,b)∈A and a hypothesis of the outranking aSb. The credibility of outranking is usually defined by the credibility index σ(a,b), as follows:

σ(a,b) = C(a,b) × ∆(a,b), (2.1)
where C(a,b) is a concordance degree and ∆(a,b) is a component taking into account discordance degrees on particular criteria. For the sake of simplicity, in all formulae that follow, we suppose that all thresholds are constant and that criteria are identified by their indices.

Let us denote by k j the weight assigned to criterion g j , j=1,…,n; it represents a relative importance of criterion g j within family F.

The concordance degree C(a,b) takes account of the strength of the coalition of criteria being in favor of the assertion "a is at least as good as b", i.e. in favor of aSb. This coalition is composed of two subsets of criteria:

• C(aSb) -composed of criteria being clearly in favor of aSb, i.e. such that g j (a) ≥ g j (b) -q j , • C(bQa) -composed of criteria that do not oppose to aSb, while being in an ambiguous position with respect to this assertion; these are those criteria for which a weak preference relation bQa holds; i.e. such that g j (b) -p j ≤ g j (a) < g j (b) -q j , Consequently, the concordance degree is defined as

( ) ( ) () ∑ ∑ ∑ = ∈ ∈ ϕ + = n j j bQa j j j aSb j j k k k b , a C 1 C C
, where

( ) ( ) ( ) j j j j j j q p p b g a g - - - = ϕ . (2.2) [ 1 0, j ∈ ϕ ] ]
is a coefficient that decreases the contribution of criterion g j to the concordance degree as far as the ambiguity increases.

Remark that C

, where

( ) [ 1 0, b , a ∈ ( ) 0 = b , a C if g j (a) ≤ g j (b) -p j , j=1,…,n (b is strictly
preferred to a on all criteria), and ( )

1 = b , a C if g j (a) ≥ g j (b) -q j , j=1,…,n (a outranks b on all criteria).
Let us consider now those criteria for which a finite veto threshold v j has been specified. Each one of these criteria is associated with a degree of discordance defined as

( ) ( ) ( ) () ( ) () [ ] ( ) () () () () ()      - > - ≤ < - - - - - ≤ = ' v b g a g ' v b g a g v b g ' v v a g ' v b g v b g a g , b , a d j j j j j j j j j j j j j j j j j if 0 if if 1 , (2.3)
where is called pre-veto threshold, v (j=1,…,n). Originally [START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF],

' v j j j j p ' v ≥ > j j p ' v = ,
however, in some situations it might be desirable to keep when , which would make . Such situations were pointed out as well in methodological studies [START_REF] Mousseau | Valued outranking relations in ELECTRE providing manageable disaggregation procedures[END_REF][START_REF] Perny | Multicriteria filtering methods based on concordance/non-discordance principles[END_REF][START_REF] Roy | Paradigms and challenges[END_REF][START_REF] Słowiński | Rough classification with valued closeness relation[END_REF], as in practical applications [6].

( ) = b , a d j 0 () () j j p b a g - j g < j j p ' v >
There are two ways of defining ∆(a,b), either as:

( ) ( ) ( ) ( ) ∏ ∈ - - = ∆ b , a J j j b , a C b , a d b , a 1 1 , (2.4)
where if and only if

( b , a J j ∈ ) ( ) ( ) b , a C b , a j ≥ d
, which is the original formula, or as

( ) ( ) ( ) ∏ ∈ - = ∆ F j j b , a d b , a 1 .
(2.5)

When using formula (2.5), one might wish to avoid situation where veto intervenes prematurely without sufficient justification; then it is recommended to set for all those criteria for which

j j p ' v > ∞ ≠ j v .
It follows from the above formulae that ( ) [ ]

1 0, b , a ∈ σ .

Handling of preference reinforcement thresholds

Principles and requirements

The goal is to give to certain criteria g j , j∈F, the possibility of increasing their relative importance in the definition of concordance degree C(a,b) when the difference g j (a)g j (b) exceeds a given value called reinforced preference threshold. The handling of preference reinforcement thresholds should satisfy the following requirements:

i) all things equal elsewhere, if for any criterion g j , j∈F, the reinforced preference threshold is crossed, then the concordance degree C(a,b) cannot decrease,

Proposed formula

Let rp j denote the reinforced preference threshold for criterion g j . When this threshold is crossed, the importance coefficient k j in formula (2.2) should be replaced by ω j k j , where ω j >1 is called reinforcement factor. Let C(aRPb) denote the set of criteria for which g j (a) > g j (b) + rp j . The concordance degree in then defined as (3.1)

( ) ( ) ( ) ( ) ( ) ( ) ( ) ∑ ∑ ∑ ∑ ∑ - ∈ ∈ ∈ - ∈ ∈ + ω ϕ + + ω =

Proofs of requirements

Proof of i). Let (a,b)∈A such that C(a,b)=N/D. Remark that N≤D. Consider criterion g j such that g j (b) -q j ≤ g j (a) ≤ g j (b) + rp j . Suppose that g j (a) has grown such that g j (a) > g j (b) + rp j . Then the concordance degree becomes

( ) ( ) ( ) j j j j k D k N b , a ' C 1 1 - ω + - ω + = . ( )( ) ( ) ( ) ( ) ( ) j j j j j j j j k N k D D N k D k N b , a C b , a ' C 1 1 1 1 - ω ≥ - ω ⇔ ≥ - ω + - ω + ⇔ ≥
, which is true because N≤D.

Proof of ii).

According to i), requirement ii) holds when g j (a) -g j (b) on criterion g j , j∈F, is crossing rp j . In all other cases, the increase of g j (a) -g j (b) keeps the denominator of (3.1) unchanged. Since in such cases nominator is a non-decreasing function of each g j (a) -g j (b), the requirement is satisfied.

Proof of iii).

If a outranks b on all criteria, then C(bQa) = ∅ and C(aSb) = F; then, independently of C(aRPb), the nominator of (3.1) becomes equal to the denominator. Suppose now that there exists at least one criterion g j , j∈F, for which g j (a) < g j (b) -q j . In this case, j does not belong neither to C(aRPb) nor to C(aSb), however, it can belong to C(bQa). Even so, the nominator of (3.1) is strictly smaller that the denominator, thus C(a,b)<1.

Handling of counter-veto thresholds

Principles and requirements

The goal is to give to certain criteria g j , j∈F, the possibility of decreasing the veto effect on discordant criteria when the difference g j (a) -g j (b) exceeds a given value called counter-veto threshold. By definition, case a) if no veto effect intervenes on any criterion (∆(a,b)=1, see Section 2), then the counter-veto of g j is inactive, case b) if veto effects intervene on some criteria (∆(a,b)<1), then the counter-veto of g j is weakening these effects.

The handling of counter-veto thresholds should satisfy the following requirements: i) all things equal elsewhere, if the number of criteria g j , j∈F, for which the counter-veto threshold is crossed, increases from k to k+1, then the credibility of outranking σ(a,b) cannot decrease, i.e. σ(a,b) is a monotone, non-decreasing function of k, ii) if there exists a discordant criterion g i , i∈F, which does not produce a veto effect, then, all things equal elsewhere, withdrawing this criterion from family F should keep increasing the credibility of outranking σ(a,b), whatever number k of criteria for which the counter-veto threshold has been crossed, iii) if for a discordant criterion g i , i∈F, the discordance degree d i (a,b) increases, then, all things equal elsewhere, the credibility of outranking σ(a,b) should remain non-increasing, whatever the number k of criteria for which the counterveto threshold has been crossed, i.e. σ(a,b) is a monotone, non-increasing function of d i (a,b).

Proposed formula

Let cv j denote the counter-veto for criterion g j and k the number of criteria for which the counter-veto threshold has been crossed. We propose to define the index of the credibility of outranking σ(a,b) as In each of these cases, withdrawing g i from family F keeps ∆(a,b) unchanged. This withdrawal changes n to n-1, thus the exponent decreases from 1-k/n to 1-k/(n-1),

( ) ( ) ( ) [ ] ( ) n / k b , a b , a C b , a - ∆ × = σ 1 . ( 4
which makes ( ) [ ] ( ) ( ) [ ] ( ) ( ) 1 1 1 - - - ∆ ≤ ∆ n / k n / k b , a b , a
. On the other hand, withdrawing g i from family F increases C(a,b) because its denominator decreases by k i while its nominator remains unchanged. Consequently, the credibility of outranking σ(a,b) is increasing.

Proof of iii).

Conclusions

The aim of this paper was to handle the effect of reinforced preference defined in 3.1 and the effect of counter-veto defined in 4.1. We have shown that formula (4.1) takes into account these effects in accordance with requirements expressed in 3.2 and 3.3.

Let us remark that these effects concern only those criteria for which, as soon as action a is "judged very strongly preferred" to action b, one wishes that the credibility of outranking of a over b is greater than the one for the case where (all things equal elsewhere) the preference is not "judged very strong".

In all formulae considered in the paper, all thresholds have been supposed constant for the sake of simplicity only, but one can easily re-write these formulae with variable thresholds.

For any criterion g j , j∈F, the two thresholds rp j and cv j can be chosen equal, and, moreover, one may wish to consider only one of the two effects; deleting an effect means giving to the corresponding threshold an infinite or very large value. Consequently, no order relation is imposed between these two thresholds.

The new formula (4.1) for the index of the credibility of outranking can be substituted for similar formulae used in original versions of ELECTRE III and ELECTRE TRI [START_REF] Figueira | ELECTRE methods[END_REF].

The assignment of values to the new thresholds rp j and cv j can be done in a constructive way of thinking about the model of decision problem at hand. One can use for this some protocols of inquiry similar to those proposed for assigning appropriate values to indifference and preference thresholds [START_REF] Roy | Aide multicritère à la décision: Méthodes et cas[END_REF], or to the weights [START_REF] Figueira | Determining the weights of criteria in the ELECTRE type methods with a revised Simos' procedure[END_REF]. These protocols involve few easy questions which do not require from the addressee to speculate about completely unrealistic situations. Another way could be to proceed via disaggregationaggregation approach, so as to get thresholds rp j and cv j as compatible as possible with some exemplary pairwise comparisons of few real actions [START_REF] Mousseau | Inferring an ELECTRE TRI model from assignment examples[END_REF].

The way of introducing the two new effects is consistent with the handling of purely ordinal preference scales. Each of the two new thresholds is like a frontier representing a qualifier without any reference to a notion of quantity. The weights remain intrinsic weights, and do not become substitution rates, the indifference and preference thresholds play exactly the same role as before.

The new formula could also be used outside ELECTRE methods, for example, as similarity or closeness index [START_REF] Słowiński | Rough classification with valued closeness relation[END_REF][START_REF] Słowiński | Similarity relation as a basis for rough approximations[END_REF]13], or as a filtering operator [START_REF] Perny | Multicriteria filtering methods based on concordance/non-discordance principles[END_REF].

  ii) C(a,b) should remain a monotone non-decreasing function with respect to differences g j (a) -g j (b) for each j∈F, iii) C(a,b) should remain equal to 1 if and only if a outranks b on all criteria.

. 1 ) 1 ) 4 . 3 .

 1143 In this formula, C(a,b) can be defined by either (2.2) or (3.1), and ∆(a,b) by either (2.4) or(2.5). This formula satisfies both properties expressed as case a) and case b) in the definition. As to case a), for ∆(a,b)=1, ( ) [ ] k. As to case b), , whatever k, since ∆(a,b)<1. Proofs of requirements Proof of i). Since ∆(a,b)≤1, , non-decreasing function of k. Proof of ii). We consider two cases related to the definition of ∆(a,b): • if ∆(a,b) is defined by (2.4), then discordant criterion g i , i∈F, has to verify 0≤d i (a,b)≤C(a,b), • if ∆(a,b) is defined by (2.5), then discordant criterion g i , i∈F, has to verify d i (a,b)=0.

  Independently of the definition of ∆(a,b), the increase of any d i (a,b) cannot increase ∆(a,b) and, consequently,