Claudia Kubicek
email: claudia.kubicek@psychol.uni-giessen.de

Judit Gervain

Anne Hillairet De Boisferon

Olivier Pascalis

Hélène Loevenbruck

Gudrun Schwarzer

The influence of infant-directed speech on 12-month-olds' intersensory perception of fluent speech

Keywords: infant-directed speech, audio-visual speech perception, intersensory, infants, perceptual narrowing

come

Introduction

Infants are born into a social world and grow up as social beings. In this social world they experience human speech from the beginning. Infants are especially fascinated by speech sounds specifically addressed to them, that is, infant-directed (ID) speech. ID speech is typically characterized by a variety of linguistic and prosodic modifications that are often assumed to facilitate infants' speech processing. Speech processing typically involves the matching of information provided by at least two sensory systems: hearing and vision. The remarkable ability to audio-visually match vowels or syllables (i.e., short speech segments) has been found in infants before 6 months of age [START_REF] Kuhl | The Bimodal Perception of Speech in Infancy[END_REF][START_REF] Mackain | Infant Intermodal Speech-Perception Is a Left-Hemisphere Function[END_REF][START_REF] Patterson | Matching phonetic information in lips and voice is robust in 4.5-month-old infants[END_REF], 2003;[START_REF] Pons | Narrowing of intersensory speech perception in infancy[END_REF]. Despite the fact that infants experience face-to-face communication mostly in a fluent sequence of utterances, to date, only few studies have focused on infants' intersensory perception of fluent speech, and provided mixed results, in particular in older infants. While one study found 10-to 12-month-olds to perceive the correspondence between native audio-visual fluent speech only [START_REF] Lewkowicz | Recognition of amodal language identity emerges in infancy[END_REF], another study could not find any evidence for this pattern either for native, or for nonnative speech in infants at that age [START_REF] Kubicek | Face-scanning behavior to silently-talking faces in 12-monthold infants: The impact of pre-exposed auditory speech[END_REF]. As the two studies differ in the speaking style used, that is, ID speech in [START_REF] Lewkowicz | Recognition of amodal language identity emerges in infancy[END_REF], but not in Kubicek et al.'s (2013) work, we assume that ID speech might have facilitated infants' matching performance. However, the speculated contribution of ID speech to 12-month-olds' intersensory speech perception is still unclear and has not yet been addressed. Thus, the motivation of the present study is to investigate whether ID speech does indeed facilitate 12month-olds' intersensory perception of native and non-native fluent speech.

Characteristics of ID speech

Adults who communicate with infants automatically tend to modify their speech in certain characteristic ways [START_REF] Fernald | A Cross-Language Study of Prosodic Modifications in Mothers and Fathers Speech to Preverbal Infants[END_REF] resulting in a distinct speaking style referred to as ID speech. Although cross-linguistic and cross-cultural differences have been observed in the prosodic modifications associated with ID speech [START_REF] Ingram | The Cultural Basis of Prosodic Modifications to Infants and Children -a Response to Fernalds Universalist Theory[END_REF], ID speech is generally characterized by an exaggerated prosody [START_REF] Fernald | Expanded Intonation Contours in Mothers Speech to Newborns[END_REF][START_REF] Uther | Do you speak E-NG-L-I-SH? A comparison of foreigner-and infant-directed speech[END_REF]. In many of the languages that have been studied, ID-speech is characterized by an increase in pitch mean and pitch range relative to adult-directed (AD) speech.

Additionally, while ID speech sentences tend to be shorter and often grammatically more simplified or more incomplete than AD sentences [START_REF] Newport | Mother, I'd rather do it myself: Some effects and non-effects of maternal speech style[END_REF], they are slower in tempo, separated by longer pauses, and contain more repetitions of words and phrases [START_REF] Fernald | Common Themes and Cultural Variations in Japanese and American Mothers Speech to Infants[END_REF][START_REF] Papousek | Didactic Adjustments in Fathers and Mothers Speech to Their 3-Month-Old Infants[END_REF][START_REF] Stern | The Prosody of Maternal Speech -Infant Age and Context Related Changes[END_REF]. From birth on infants prefer to listen to ID speech [START_REF] Cooper | Preference for Infant-Directed Speech in the 1st Month after Birth[END_REF][START_REF] Fernald | 4-Month-Old Infants Prefer to Listen to Motherese[END_REF][START_REF] Mcroberts | The Role of Verbal Repetition in the Development of Infant Speech Preferences From 4 to 14 Months of Age[END_REF][START_REF] Werker | A Cross-Language Investigation of Infant Preference for Infant-Directed Communication[END_REF] suggesting that ID speech effectively elicits and holds infants' attention. Likewise, the facial movements made during ID speech differ from AD speech [START_REF] Chong | Three facial expressions mothers direct to their infants[END_REF][START_REF] Shepard | Distinct Facial Characteristics Differentiate Communicative Intent of Infant-Directed Speech[END_REF] and display characteristics such as exaggerated lip movement [START_REF] Green | Lip Movement Exaggerations During Infant-Directed Speech[END_REF], exaggerated smiles, raised eyebrows, and wide eyes [START_REF] Swerts | Visual prosody of newsreaders: Effects of information structure, emotional content and intended audience on facial expressions[END_REF][START_REF] Werker | Infant Preference for Both Male and Female Infant-Directed Talk -a Developmental-Study of Attentional and Affective Responsiveness[END_REF] which are highly salient to infants. These dynamic visual properties that accompany the acoustic ID speech message may further capture infants' attention and may not only facilitate infants' language acquisition [START_REF] Golinkoff | Infant-directed speech facilitates lexical learning in adults hearing Chinese: Implications for language acquisition[END_REF][START_REF] Graf Estes | Infant-directed prosody helps infants map sound to meanings[END_REF][START_REF] Ma | Word learning in infantand adult-directed speech[END_REF][START_REF] Singh | Influences of Infant-Directed Speech on Early Word Recognition[END_REF][START_REF] Zangl | Increased brain activity to infant-directed speech in 6-and 13-month-old infants[END_REF] but may also contribute, in particular, to infants' processing of intersensory speech. Although this assumption is speculative, as it is still understudied, a study by Kaplan, Jung, Ryther, and Zarlengo-Strouse (1996) provided some evidence for this hypothesis as they found that 4-month-olds learned an intersensory association between speech segments and faces under an ID speech but not an AD speech condition. Moreover, a recent study by [START_REF] Kim | Detecting 'infant-directedness' in face and voice[END_REF] showed that 3-and 5-month-old infants preferred to look at a face talking in an ID speaking style over a face speaking AD speech, highlighting the influence of ID speech on infants' visual attention to talking faces.

Infants' intersensory perception of speech

With respect to the perception of the joint information carried by audio and visual speech streams, infants as young as 2 months (e.g., [START_REF] Patterson | Two-month-old infants match phonetic information in lips and voice[END_REF], and 4.5-to 6month-olds [START_REF] Kuhl | The Bimodal Perception of Speech in Infancy[END_REF][START_REF] Mackain | Infant Intermodal Speech-Perception Is a Left-Hemisphere Function[END_REF][START_REF] Patterson | Matching phonetic information in lips and voice is robust in 4.5-month-old infants[END_REF] have been found to match audio and visual stimuli corresponding to specific vowels and disyllables in an intermodal matching task [START_REF] Spelke | Perceiving Bimodally Specified Events in Infancy[END_REF]. Here, infants are typically presented with two side-by-side video images of a person silently articulating in synchrony, for instance, the vowels /i/ and /a/ while the corresponding sound of one vowel is simultaneously played through a central speaker. If infants exhibit longer looking times to the audio-matching visible speech, cross-modal matching is successfully detected. By using a variant of the intermodal matching task, [START_REF] Pons | Narrowing of intersensory speech perception in infancy[END_REF] demonstrated that 6-month-old infants were able to perceive the intersensory coherence of audio-visual syllables presented sequentially, suggesting that they were capable of performing cross-modal transfer of information. In this kind of paradigm, sequential presentation of auditory and visual stimuli rules out the possibility that infants may simply detect sound-face matching based on audio-visual synchrony, that is, on purely temporal grounds (simply knowing that an open mouth produces louder sounds, for instance), without using more language-based processing mechanisms. By using the same paradigm, a recent study by [START_REF] Lewkowicz | Recognition of amodal language identity emerges in infancy[END_REF] addressed the question of whether infants are also able to match audio-visual fluent speech. The authors tested English-learning infants' ability to orient toward side-by-side silent videos of a Spanish-English bilingual woman talking in a highly prosodic style (or ID speech).

Spanish was presented on one side and English on the other side before (baseline condition)

and after (test condition) auditory-only familiarization with one of the two languages, respectively. The study revealed that 10-to 12-month-old infants showed a novelty preference for the non-native (Spanish) visual speech after they were auditory-only familiarized to their native language (English). The authors assume that infants only recognized the amodal identity of their native language, as a result of perceptual narrowing, that is, a decline in the sensitivity to non-native sensory inputs (for recent reviews, see [START_REF] Lewkowicz | Early Experience and Multisensory Perceptual Narrowing[END_REF][START_REF] Maurer | Perceptual Narrowing During Infancy: A Comparison of Language and Faces[END_REF]. Moreover, Lewkowicz and Pons also indicate some audio-visual matching ability in 10-to 12-month-old infants, at least in response to infants' native speech. However, this finding is in contrast with [START_REF] Kubicek | Face-scanning behavior to silently-talking faces in 12-monthold infants: The impact of pre-exposed auditory speech[END_REF] who found by using a nearly identical experimental procedure that 12-month-old German-learning infants failed to show any visual preferences for either German or French silently-speaking faces after auditory input.

Methodological issues might have caused those contradictory results, such as, for example, the properties of the languages used, since the contrast between German and French is different in many ways from the contrast between English and Spanish. Importantly, in contrast to [START_REF] Kubicek | Face-scanning behavior to silently-talking faces in 12-monthold infants: The impact of pre-exposed auditory speech[END_REF] 1 , [START_REF] Lewkowicz | Recognition of amodal language identity emerges in infancy[END_REF] used a script that was articulated in a highly prosodic style, that is, in ID speech. Thus, it could be speculated that the 10-to-12-month-olds' in [START_REF] Lewkowicz | Recognition of amodal language identity emerges in infancy[END_REF] study recognized the amodal identity of their native language because the speaking style might have played a role in responsiveness. Due to its highly salient properties, ID speech may have particularly directed infants' attention toward the stimuli. In addition, ID speech may have enhanced the salience of the relevant matching cues (i.e., auditory and facial speech cues) across the modalities, which might have facilitated infants' intersensory response.

The current study

The present study intended to investigate whether ID speech contributes to 12-montholds' intersensory matching of audio-visual native and non-native fluent speech.

In Experiment 1, by using [START_REF] Lewkowicz | Recognition of amodal language identity emerges in infancy[END_REF] procedure, we presented German-learning infants with visual and auditory speech information presented sequentially in order to control for matching effects due to temporal synchrony. In this task, infants were first exposed to a side-by-side presentation of silent videos of one woman talking German on one side and French on the other side (baseline condition). An auditory-only familiarization followed, after which the test started, with the initial silent videos presented again. The German and French stimuli were articulated in AD speaking style. Based on the assumption that infants' looking behavior indicates cross-modal matching, infants were considered to audio-visually match fluent speech if they exhibited longer looking times to the audiomatching visual stimuli during the test trials as compared to the baseline trials.

In Experiment 2, when infants were exposed to ID speech stimuli, we expected the infants to perceive the intersensory correspondence of audio-visual speech by showing a greater proportion of looking time, during the test trials as compared to the baseline trials, toward the visual stimuli corresponding to the audio stimuli they previously heard. According to the perceptual narrowing view, we additionally expected the 12-month-old infants to respond to native auditory speech only. Audio-visual matching with native ID speech would provide evidence for the facilitatory effect of ID speech on intersensory speech perception.

Experiment 1

Method

Ethics Statement

The present study was conducted in accordance to the German Psychological Society (DGPs) Research Ethics Guidelines. The Office of Research Ethics at the University of Giessen approved the experimental procedure and the informed consent protocol. Written informed consents were obtained from the infants' parents prior to their participation in the study.

Participants

The sample consisted of a total of 49 monolingual German-learning 12-month-old infants (M age = 372 days; SD = 11 days; 22 females). All infants were full-term with no visual or auditory deficits, as reported by parents. The data from 12 additional infants were discarded from the final sample due to extreme fussiness.

Stimuli and Apparatus

In Experiments 1 and 2, visual stimuli were silent video clips of two female bilingual German-French speakers. The speakers were recorded against a blue background, looking directly into the camera, while reciting German and French sentences in a similar speaking rate 2 . All videos were resized identically to ensure uniformity. Each of the 30-second video clips showed a full-face image of the speaker and measured 20.6 cm x 18 cm when displayed side-by-side on the monitor, separated by an 11-cm gap. Both videos, French and German, were edited to make sure that the first mouth opening was synchronized. The audio stimuli were the soundtracks extracted from the video recordings (65dB ± 5dB).

Two sets of stimuli were created: adult-directed (Experiment 1) and infant-directed stimuli (Experiment 2).

Adult-directed (AD) stimuli:

The German and French sentences were adapted from the nursery rhyme "Goldilocks and the three bears" and spoken with a neutral expression in an AD manner, except for the beginning and the end of the story during which the speakers slightly smiled. In both languages, the story consisted of 11 sentences.

Procedure

2 Recording took place in Germany, i.e., the bilingual speakers were German-dominant and were rated by French participants (in an informal test) as speaking the French version with a German accent.

Each infant was tested individually in a baby lab. Caregivers gave written informed consent for their infant to participate. Parents were told to keep their eyes closed and to refrain from talking for the duration of the experiment. The infants were seated on the caregiver's lap at a distance of 60 cm in front of a 22-inch monitor. Stimuli were presented using E-Prime 2.0 software (Psychology Software Tools, Sharpsburg, PA).

Following [START_REF] Lewkowicz | Recognition of amodal language identity emerges in infancy[END_REF], there were six trials (see Figure 1): two silent baseline trials, a first auditory-only familiarization trial followed by a silent test trial during which the two initial silent faces were presented, and a second auditory-only familiarization trial followed by a silent test trial. The left-right position of the videos was counterbalanced across infants, and side of language presentation was switched across baseline and test trials, respectively. In the 3 rd and 5 th trial (auditory-only familiarization trial) half of the infants were presented with a French voice while watching an attention getter, while the other half heard German. Infants were randomly assigned to one of the two auditory condition groups (German or French). A video camera (specialized for low light conditions) was used to record the infants' looking behavior. The film was then digitized and coded frame by frame by two independent observers who were blind to specific hypotheses. The inter-rater reliability was .92.

Results and Discussion

Lewkowicz and Pons (2013), we analyzed looking during the first 20 seconds of baseline and test trials. An analysis of looking times during baseline trials revealed that infants did not show an initial preference for either of the visual stimuli (VS): M GermanVS = 16.0 seconds vs. M FrenchVS = 16.2 seconds, t(48) = -0.22, ns.

To determine whether the infants showed intersensory matching, we computed preference scores by dividing the looking time to one face (German talking face or French talking face) by the amount of total looking time (sum of looking times at the German and French talking faces) within baseline and test trials, respectively. We then compared the preference scores for the audio-matching face of baseline to test trials by submitting these scores to a mixed ANOVA with "Trial Type" (baseline, test) as a within-subjects factor and "Auditory Group" (French, German) as a between-subjects factor. The ANOVA revealed no significant differences, indicating that 12-month-old infants did not show any visual preference (Auditory German Group: M Base_German = 50.1%, SD = 9.3%, M Test_German = 48.1%, SD = 8.0%; Auditory French Group: M Base_French = 51.4%, SD = 10.5%, M Test_French = 50.6%, SD = 11.9%).

Thus, when AD stimuli were used, 12-month-olds did not show an intersensory response to auditory-visual fluent speech when auditory and visual stimuli were presented sequentially. To examine whether ID speech facilitates matching, infants' matching performance was tested in Experiment 2, using the same procedure, with stimuli spoken in an ID style.

Experiment 2

Method

Participants

The sample consisted of a total of 47 monolingual German-learning 12-month-old infants (M age =369 days; SD = 11 days; 21 females). All infants were full-term with no visual or auditory deficits, as reported by parents. The data from 6 additional infants were excluded due to extreme fussiness.

Stimuli, Procedure and Apparatus

We used the same procedure and apparatus as in Experiment 1 except for the use of ID speech stimuli.

Infant-directed (ID) stimuli:

For the ID stimuli, we slightly modified the sentences used in Experiment 1 in order to meet most of the characteristics of ID speech. We used 11 sentences, which were shorter (half the amount of syllables compared to AD stimuli), had a simplified grammatical structure, contained more repetitions of words and phrases, and were produced with a slower tempo and longer pauses [START_REF] Fernald | Common Themes and Cultural Variations in Japanese and American Mothers Speech to Infants[END_REF][START_REF] Papousek | Didactic Adjustments in Fathers and Mothers Speech to Their 3-Month-Old Infants[END_REF][START_REF] Stern | The Prosody of Maternal Speech -Infant Age and Context Related Changes[END_REF]. The ID stimuli were constructed to have the same duration as the AD stimuli. The sentences were spoken in a highly prosodic style. In both languages, audio ID speech stimuli contained higher mean fundamental frequency and more variation in frequency range (M German = 268.9 Hz, SD German = 75.0 Hz, F 0 Range German = 239.1 Hz; M French = 274.4 Hz, SD French = 61.9 Hz, F 0 Range French = 225.5 Hz) than did AD speech stimuli (M German = 220.3 Hz, SD German = 51.6 Hz, F 0 Range German = 180.8 Hz; M French = 236.6 Hz, SD French = 48.0 Hz, F 0 Range French = 180.5 Hz), mirroring the acoustic differences between ID and AD speech reported in the literature [START_REF] Fernald | Intonation and Communicative Intent in Mothers Speech to Infants -Is the Melody the Message[END_REF][START_REF] Fernald | Expanded Intonation Contours in Mothers Speech to Newborns[END_REF]. The stimuli were also accompanied by facial movements that have been reported to display ID speech characteristics, such as exaggerated mouth movements, greater teeth visibility, wide eyes, raised eyebrows, and smiling eyes and lips [START_REF] Chong | Three facial expressions mothers direct to their infants[END_REF][START_REF] Shepard | Distinct Facial Characteristics Differentiate Communicative Intent of Infant-Directed Speech[END_REF].

The visual German and French ID and AD stimuli were also rated by 22 native German-speaking undergraduate students to assess infant-vs. adult-directedness by using the ID/AD scale developed by [START_REF] Shepard | Distinct Facial Characteristics Differentiate Communicative Intent of Infant-Directed Speech[END_REF]. The scale ranged from 1 (definitely infantdirected) to 3 (neither adult nor infant-directed) to 5 (definitely adult-directed). Adultdirected was described as 'the type of speech one uses when talking to an adult, like the way the experimenter is talking to you'. Infant-directed was described as 'the type of speech one uses when talking to an infant (a baby between the ages of newborn to one year)'. A score of 0 was used to denote 'I don't know'. However, none of the participants had chosen the score 0 ('I don't know'). In general, the ID speech stimuli were judged to be infant-directed (M = 1.53, SD = 0.25) and the AD speech stimuli were judged as adult-directed (M = 4.17, SD = 0.43), t(21) = 24.81, p < .001.

Results

The first analysis revealed that infants did not show a preference for either of the visual speeches during baseline: M GermanVS = 16.9 seconds vs. M FrenchVS = 18.9 seconds, t(47) = -1.68, ns.

As in Experiment 1, we computed preferential looking scores, and submitted these scores to a mixed ANOVA with "Trial Type" (baseline, test) as a within-subjects factor and "Auditory Group" (French, German) as a between-subjects factor. The ANOVA revealed a significant Trial Type x Auditory Group interaction, F(1, 45) = 7.04, p < .05, µ 2 = 0.13, indicating that infants' intersensory matching ability depended on the language they were auditorily familiarized with. Separate two-tailed t-tests revealed that infants looked longer at German visual speech after German auditory-only familiarization compared to looking at German visual speech during baseline, t(24) = -2.79, p < .05, d = 0.56. No such difference was found in infants who were auditory familiarized with French, t(21) = 0.77, ns (see Figure 2).

Comparison between Experiment 1 and 2

In order to examine whether speaking style indeed influenced infants' looking behavior, a mixed ANOVA comparing Experiment 1 and 2 with "Trial Type" (baseline, test) as a within-subjects factor, "Speaking Style" (ID, AD), and "Auditory Group" (French, German) as between-subjects factors was conducted. The ANOVA revealed a significant Speaking Style x Trial Type x Auditory Group interaction, F(1, 92) = 4.56, p < .05, µ 2 = .05, indicating that infants' intersensory matching ability depended on the speaking style and the language they were auditorily familiarized with.

Therefore, the findings of Experiment 1 and 2 suggest that ID speech might indeed facilitate 12-month-olds' intersensory matching ability, but only with respect to their native language.

General Discussion

The principal motivation of the present study was to investigate the influence of ID speech on 12-month-olds' intersensory perception of native and non-native fluent speech.

Experiment 1 revealed that infants exposed to AD speech did not show any sensitivity to either German or French visual stimuli in response to the auditory input. In line with our expectation, Experiment 2 revealed that when sentences were spoken in an ID style, infants perceived the intersensory coherence between audible and visible attributes of fluent speech.

However, infants' intersensory response was restricted to their native language.

The differential efficiency of ID vs. AD stimuli expressed by the fact that infants only showed a matching ability when sentences were spoken in an ID style supports the hypothesis [START_REF] Fernald | The perceptual and affective salience of mothers' speech to infants[END_REF] that ID speech contributes to more efficient information processing in infants.

Our results are in line with claims related to the facilitation effect that ID speech is said to have on speech processing [START_REF] Liu | An association between mothers' speech clarity and infants' speech discrimination skills[END_REF] and language acquisition [START_REF] Ma | Word learning in infantand adult-directed speech[END_REF][START_REF] Singh | Influences of Infant-Directed Speech on Early Word Recognition[END_REF][START_REF] Thiessen | Infant-directed speech facilitates word segmentation[END_REF]. They are also consistent with prior research on the influence of ID speech on infants' intersensory face-voice associations [START_REF] Kaplan | Infant-directed versus adult-directed speech as signals for faces[END_REF] and extend these results, as they confirm facilitation of ID speech in infants' intersensory perception of fluent speech [START_REF] Lewkowicz | Recognition of amodal language identity emerges in infancy[END_REF]. However, our findings did not exactly meet the results of Lewkowicz and Pons' study (2013). Just as in [START_REF] Pons | Narrowing of intersensory speech perception in infancy[END_REF], infants in the present study looked longer to the audio-matching visual speech. In contrast, the infants in Lewkowicz and Pons' study (2013) showed a novelty preference and looked longer toward non-native visual speech after native auditory language input. Those contradictory results might have been caused by methodological differences, such as the use of different language contrasts, the infants' native language, different age ranges, and stimuli used. More notable than this minor difference, however, is the similarity that both studies observed a preference for one of the visual stimuli in response to native auditory-only speech spoken in an ID manner.

The question remains as to why ID style facilitates the processing of auditory-visual fluent speech more than AD style does. One speculation is that the characteristic auditory (or acoustic) and visual (or articulatory) properties of ID speech [START_REF] Fernald | Acoustic Determinants of Infant Preference for Motherese Speech[END_REF][START_REF] Shepard | Distinct Facial Characteristics Differentiate Communicative Intent of Infant-Directed Speech[END_REF] improve infants' attention to speech cues and are easier to process [START_REF] Soderstrom | Beyond babytalk: Re-evaluating the nature and content of speech input to preverbal infants[END_REF]. It has also been shown that ID speech elicits increased neural activity compared to AD speech in 6-and 13-month-olds for familiar words [START_REF] Zangl | Increased brain activity to infant-directed speech in 6-and 13-month-old infants[END_REF]. Only the older infants (13-month-olds) showed an increased response to ID speech for both familiar and unfamiliar words. These event-related potential data point to developmental changes in the response to ID speech around the first year [START_REF] Hayashi | Developmental change in auditory preferences for speech stimuli in Japanese infants[END_REF]. Thus, it could be speculated that ID speech enters more into the processing of audio-visual speech than AD speech does, especially in infants toward the end of the first year.

The aforementioned speculation could explain the behavior of the 12-month-olds in Experiment 1, who showed neither visual preference nor auditory-visual matching when exposed to AD speech. Infants toward the end of the first year might be less attentive to visual AD speech cues [START_REF] Kubicek | Face-scanning behavior to silently-talking faces in 12-monthold infants: The impact of pre-exposed auditory speech[END_REF][START_REF] Sebastian-Galles | A Bilingual Advantage in Visual Language Discrimination in Infancy[END_REF][START_REF] Weikum | Visual language discrimination in infancy[END_REF] and therefore do not notice the differences between the visual cues carried by two different languages. Following this hypothesis, the failure to match audible and visible AD speech could have been caused by the failure to visually discriminate the languages. Less attentiveness to the visual modality of speech is probably caused by an increased understanding of auditory speech in 12-month-olds as, for instance, compared to younger infants entering the babbling stage, who rely more on the redundancies of audiovisual speech (Lewkowicz & Hansen-Tift, 2012). Younger infants at 4 and 6 months of age have been found to be sensitive to visual speech cues [START_REF] Weikum | Visual language discrimination in infancy[END_REF] and show indeed the ability to match audio-visual fluent speech (Kubicek et al., 2104).

Infants around the first year do not only improve their speech comprehension skills (e.g., for words) by parsing the auditory signal of the speech input [START_REF] Swingley | Contributions of infant word learning to language development[END_REF] but they are also more and more attentive to facial cues obtaining social information [START_REF] Brooks | The importance of eyes: How infants interpret adult looking behavior[END_REF][START_REF] Moll | 12-and 18-month-old infants follow gaze to spaces behind barriers[END_REF]. Moreover, 12-month-olds have been shown to be sensitive to emotional affects in speakers. In this line, it has been shown that vocal-only cues contribute more to social referencing than the visual facial expression of a speaker in 12month-olds [START_REF] Baldwin | The ontogeny of social information gathering[END_REF][START_REF] Mumme | Infants' responses to facial and vocal emotional signals in a social referencing paradigm[END_REF][START_REF] Vaish | Is visual reference necessary? Contributions of facial versus vocal cues in 12-months-olds' social referencing behavior[END_REF]. This suggests that infants at this age might be more experienced in processing auditory speech information. Considered in the context that the infants of the present study did not show audio-visual matching due to less attention to the relevant (visual) matching cues, it could thus be speculated that the typical characteristics of ID speech, such as easier syntactic structure, slower speaking rate, and longer pauses as well as exaggerated facial cues (mouth movements, greater teeth visibility, wide eyes, raised eyebrows, and smiling eyes and lips), might have caught infants' attention and finally might have driven 12-month-olds matching performance with regard to their native language.

In Experiment 2, 12-month-olds responded to native audio-visual ID speech only. This restriction is in line with the perceptual narrowing/tuning view [START_REF] Scott | A domain-general theory of the development of perceptual discrimination[END_REF], that is, a decline in the response to non-native input toward the end of the first year found in many perceptual domains such as perception of phonemes (e.g., [START_REF] Werker | Cross-Language Speech-Perception -Evidence for Perceptual Reorganization during the 1st Year of Life[END_REF], music perception [START_REF] Hannon | Tuning in to musical rhythms: Infants learn more readily than adults[END_REF], discrimination of other race (e.g., [START_REF] Kelly | The otherrace effect develops during infancy -Evidence of perceptual narrowing[END_REF] and other species faces (e.g., [START_REF] Pascalis | Is face processing species-specific during the first year of life?[END_REF], and audio-visual speech perception (e.g., Kubicek et al., 2014). Furthermore, the results of the present study show continuity with the data of Kubicek et al. (2014) who found that 6-month-old infants were able to perceive the intersensory coherence of native audio-visual speech only. Our results thus further support the view that perceptual narrowing is a domain general and pansensory process [START_REF] Lewkowicz | Recognition of amodal language identity emerges in infancy[END_REF][START_REF] Pons | Narrowing of intersensory speech perception in infancy[END_REF].

In conclusion, by conducting two Experiments, the current study provided, for the first time, evidence of the influence ID speech might have on the intersensory perception of fluent speech in 12-month-old infants. Exactly how ID speech may have facilitated intersensory perception cannot be determined from the current data and remains a question for future research.

Figure 1 .

 1 Figure 1. Schematic representation of the procedure used in the current study. Only the speaking style of Experiment 2 (infant-directed speech) and the German auditory condition is shown.

Figure 2 .

 2 Figure 2. Results of Experiment 2. Mean preference score (%) for German and French visual stimuli during baseline and test conditions. The two sets of bars on the left display data of infants who were auditory-only familiarized with German (native) speech. The four bars on the right side show data of French-familiarized infants. Error bars indicate the standard error of the mean. Note. * p < .05.

In this article the speaking style is described as being child-directed, which refers to the fact that a children's story was used and that the speakers smiled at the beginning and at the end of the video. With respect to facial movements and prosody, these stimuli can be clearly described as being adult-directed.

Funding

This study was supported through a grant from the German Research Foundation (Deutsche Forschungsgemeinschaft) to GS (SCHW 665/11-1) and ANR--10-FRAL-017 to OP.


Michael Poss
email: michael.poss@hds.utc.fr

Keywords: Network flows, Robust optimization, Network design, Routing set, Routing template

A comparison of routing sets for robust network design

Introduction

Given a graph and a set of point-to-point commodities with known demand values, the deterministic network design problem aims at installing enough capacity on the arcs of the graph so that the resulting network is able to route all commodities. The assumption that the exact demand values are known when planning the network expansion is not realistic. However, using population statistics and traffic measurements, we can estimate a set that contains most of the plausible outcomes for the demand values. The introduction of the uncertainty set leads to a robust optimization problem. In this context, a solution is said to be feasible for the problem if it is feasible for all demand vectors that belong to the estimated uncertainty set D, see the seminal works of [START_REF] Soyster | Convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF] and [START_REF] Ben-Tal | Robust solutions of uncertain linear programs[END_REF]. This rigid framework is computationally easy but it does not allow the model to react against the uncertainty, because optimization variables must take fixed value that are independent of the values taken by the uncertain parameters. This is a well-known drawback of the classical robust optimization framework, and it was the motivation for introducing two-stage robust optimization models where a subset of the optimization variables are fixed after observing the actual realization of the uncertain parameters [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]. This adjusting procedure is often called recourse. This two-stage approach applies naturally to network design since first stage capacity design decisions are usually made in the long term while the routing decisions depend on the realization of the demand. Hence, the routing decisions can be seen as the recourse. Imposing no restriction on the recourse is called dynamic routing in the context of robust network design problems. It has been shown by [START_REF] Minoux | Robust network optimization under polyhedral demand uncertainty is nphard[END_REF] that the robust network design with dynamic routing is N P-hard for polyhedral uncertainty.

It is known already that two-stage robust programming with unrestricted recourse is N P-hard [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]. For this reason, [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF] limit the recourse to affine functions of the uncertainties which makes the problem tractable, that is, polynomially solvable. In fact, considering special types of recourse had been used already in the context of network design. Duffield et al. [START_REF] Duffield | A flexible model for resource management in virtual private networks[END_REF] and Fingerhut et al. [START_REF] Fingerhut | Designing least-cost nonblocking broadband networks[END_REF] have independently introduced the concept of static routing for a special case of uncertainty model: after fixing the design, the routing of a commodity is allowed to change but only linearly with the variation of the commodity. Static routing has then been generalized to arbitrary uncertainty polytopes by [4,[START_REF] Ben-Ameur | Routing of uncertain demands[END_REF]. Static routing can also be seen as a single stage robust program where the set of routings paths together with the percental splitting among the paths are chosen at the same time the design decisions are made. The resulting set of paths and percental splitting is often called a routing template, which is used by all demand vectors in the uncertainty set. The use of static routing makes the robust network design problem tractable but it yields more expensive capacity allocations than the problem with dynamic routing. For instance, [START_REF] Goyal | Dynamic vs. oblivious routing in network design[END_REF] have constructed a class of graphs for which static routing can cost, in the worst case, a logarithmic factor more than dynamic routing. Static routing has been used by various authors since its introduction, including [START_REF] Altin | Provisioning virtual private networks under traffic uncertainty[END_REF][START_REF] Koster | Robust network design: Formulations, valid inequalities, and computations[END_REF][START_REF] Ordóñez | Robust capacity expansion of network flows[END_REF].

Several authors tried to introduce routing schemes that are more flexible than static routing while still being computationally easier than dynamic routing. Ben-Ameur [3] covers the demand uncertainty set by two (or more) subsets using separating hyperplanes and uses specific routings templates for each subset. The resulting optimization problem is N P-hard when no assumptions is made on the hyperplanes. Scutellá [START_REF] Scutellà | On improving optimal oblivious routing[END_REF] generalizes this idea to unrestricted covers of the uncertainty set. She allows a set of routing templates to be used conjointly so that each demand vector can be routed by at least one of the routing templates. She also introduces a procedure that works in two steps. First, an optimal capacity allocation with static routing is computed. Then, she allows to reroute part of the demand vectors according to a second routing template. Ben-Ameur and Zotkiewicz [START_REF] Ben-Ameur | Volume oriented routing[END_REF] introduce volume routing, a framework that shares the demand between two routing templates, according to thresholds. They prove that the resulting optimization problem is N P-hard and introduce two simplifications. Finally, applying the affine recourse from [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF] to robust network design problems, [START_REF] Ouorou | A model for robust capacity planning for telecommunications networks under demand uncertainty[END_REF] introduce the concept of affine routing. Recently, [START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF] study the properties of affine routing, and compare the later to the static and dynamic routings, both theoretically and empirically. They conclude that affine routing tends to yield very good approximations of dynamic routing while being computationally tractable.

In this paper, we compare theoretically the optimal capacity allocation costs provided by the affine routings from [START_REF] Ouorou | A model for robust capacity planning for telecommunications networks under demand uncertainty[END_REF], the volume routings from [START_REF] Ben-Ameur | Volume oriented routing[END_REF], and the routings based on covers of the uncertainty set in two subsets ([3] and [START_REF] Scutellà | On improving optimal oblivious routing[END_REF]). We introduce in Section 2 the robust network design problem and define formally a routing set. We model the robust network design problem with the explicit de-pendency on the routing set and formalize each of the routing frameworks studied herein. Then, we study in Section 3 how good is the cost of the optimal capacity allocation provided by each of the routing sets, and we compare these costs among the different routing sets. In Section 4, we present examples showing that it is not possible, in general, to compare some of these costs. Section 5 provides a numerical comparison of some of these routing set and we conclude the paper in Section 6.

2 Robust network design

Problem formulation

The problem is defined below for a directed graph G = (V, A) and a set of commodities K. We formalize first the concept of a routing. Then, we introduce the robust network design problem. Each commodity k ∈ K has a source s(k) ∈ V , a destination t(k) ∈ V , and a demand value

d k ≥ 0. A multi-commodity flow is a vector f ∈ R |A|×|K| +
with elements f k a where for each k ∈ K and a ∈ A, f k a denotes the amount of commodity k going through an arc a. Multi-commodity flow vectors correspond to the vectors of R |A|×|K| + that satisfy the flow conservation constraints at each node of the network:

a∈δ + (v) f k a - a∈δ -(v) f k a =    d k if v = s(k) -d k if v = t(k) 0 otherwise for each v ∈ V, k ∈ K (1)
where δ + (v) and δ -(v) respectively denote the set of outgoing arcs and incoming arcs at node v.

In this work the values of the demand vector are uncertain and belong to the closed, convex, and bounded set D ⊂ R |K| + . We call such a set an uncertainty set and any d ∈ D is called a realization of the demand. We denote by (D, R |A|×|K| ) the set of all functions from D to R |A|×|K| . Then, a routing vector is a function f ∈ (D, R |A|×|K| ) that satisfies (1) for all realizations of the demand, that is

a∈δ + (v) f k a (d) - a∈δ -(v) f k a (d) =    d k if v = s(k) -d k if v = t(k) 0 otherwise for all v ∈ V, d ∈ D, k ∈ K (2)
and that is non-negative

f k a (d) ≥ 0 for all d ∈ D. (3)
A routing with no further restrictions is called dynamic routing:

F ≡ f ∈ (D, R |A|×|K| ) | f satisfies (2) and (3) . (4)
In this paper, we are interested in using special kinds of routings. This corresponds to using specific subsets F ⊆ F . These subsets are described in the next section. In what follows, we describe the robust network design problem for explicitly defined sets of routings.

A vector x ∈ R |A| + is called a capacity allocation. A capacity allocation is said to support the set D if there exists a dynamic routing f ∈ F serving D such that for every d ∈ D the corresponding multi-commodity flow f (d) does not exceed the capacities described by x. Similarly, we say that (x, f ) supports D when both the routing f and the capacity allocation x are given. More generally, we say that (x, F ) supports D when there exists a routing f ∈ F such that (x, f ) supports D. Given an uncertainty set D and a routing set F ⊆ F, robust network design aims at providing the minimum-cost capacity allocation x and the routing f such that (x, f ) supports D:

min a∈A κ a x a RN D(F ) s.t. f ∈ F (5) k∈K f k (d) ≤ x, d ∈ D (6)
x ≥ 0, where κ a ∈ R is the cost for installing one unit of capacity on arc a ∈ A. Notice that in real applications, these costs are usually non-negative. We shall denote the optimal cost of RN D(F ) by opt(F ). Because of its convexity, set D is either a singleton or contains an infinite number of vectors. Hence, problem RN D(F ) contains in general an infinite number of variables f (d) for all d ∈ D as well as an infinite number of capacity constraints [START_REF] Ben-Ameur | Volume oriented routing[END_REF]. Moreover, the problem may not even be linear, depending on the constraints defining set F . Considering the set of all routings F, RN D(F) is a two-stage robust program with recourse following the more general framework described by [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]. The capacity design has to be fixed in the first stage, and observing a demand realization d ∈ D, we are allowed to adjust the routing f (d) arbitrarily in the second stage. In that case, (5) is replaced by (2) and (3) so that RN D(F) is a linear program, yet infinite. Whenever D is a polytope, [2] show how to provide a finite linear programming formulation for RN D(F). The formulation is based on enumerating the extreme points of D, so that its size tends to increase exponentially with the number of commodities. In fact, the problem is very difficult to solve given that only deciding whether a given capacity allocation vector x supports D is coN P-complete for general polytopes D, see [START_REF] Chekuri | Hardness of robust network design[END_REF][START_REF] Gupta | Provisioning a virtual private network: a network design problem for multicommodity flow[END_REF]. Moreover, the use of dynamic routings suffers from another drawback. It may be difficult in practice to change arbitrarily the routing according to the demand realization.

For these reasons, various authors study restrictions on the routings that can be used, introducing different subsets of routings F ⊂ F. Their hope is that opt(F ) provides a good approximation of opt(F) while yielding an easier optimization problem RN D(F ). In the next section, we present different choices of F discussed in the literature.

Note that if there exists only one path from s(k) to t(k) for a commodity k ∈ K, then all routings coincide for that commodity. Unless stated otherwise, in the following we assume that for all k ∈ K there exist at least two distinct paths p 1 , p 2 in G from s(k) to t(k), that is, two paths that differ by one arc at least.

Routings frameworks

In the next sections, we define formally the set of static routings and the routing sets from [START_REF] Ouorou | A model for robust capacity planning for telecommunications networks under demand uncertainty[END_REF]3,[START_REF] Scutellà | On improving optimal oblivious routing[END_REF][START_REF] Ben-Ameur | Volume oriented routing[END_REF].

Static routing: basic model

The simplest alternative to dynamic routing has been introduced by [START_REF] Duffield | A flexible model for resource management in virtual private networks[END_REF][START_REF] Fingerhut | Designing least-cost nonblocking broadband networks[END_REF] and has been used extensively since then, see [START_REF] Ben-Ameur | Routing of uncertain demands[END_REF][START_REF] Altin | Provisioning virtual private networks under traffic uncertainty[END_REF][START_REF] Koster | Robust network design: Formulations, valid inequalities, and computations[END_REF][START_REF] Ordóñez | Robust capacity expansion of network flows[END_REF]. This framework considers a restriction on the second stage recourse known as static routing (also called oblivious routing). Each component

f k : D → R |A| + is forced to be a linear function of d k : f k a (d) := y k a d k a ∈ A, k ∈ K, d ∈ D. (7)
Notice that [START_REF] Ben-Ameur | Robust routing and optimal partitioning of a traffic demand polytope[END_REF] implies that the flow for k is not changing if we perturb the demand for h = k. By combining (2) and ( 7) it follows that the multipliers

y ∈ R |A|×|K| + satisfy a∈δ + (v) y k a - a∈δ -(v) y k a =    1 if v = s(k) -1 if v = t(k) 0 otherwise for each v ∈ V. (8)
The flow y is called a routing template since it decides, for every commodity, which paths are used to route the demand and what is the percental splitting among these paths. We define formally the the set of all routing templates as

Y ≡ y ∈ R |A|×|K| + | y satisfies (8) , (9)
and the set of all static routings as

F stat ≡ f ∈ (D, R |A|×|K| ) | ∃y ∈ Y : f k a (d) = y k a d k a ∈ A, k ∈ K, d ∈ D .
Recall that a linear formulation is said compact if it involves polynomial numbers of variables and constraints with respect to the problem dimensions (here |V |, |A|, and |K|). An important result is that a compact linear formulation can be provided for RN D(F stat ) as long as the description of D is compact. This result follows directly from the dualization technique introduced by [START_REF] Ben-Tal | Robust solutions of uncertain linear programs[END_REF] for robust linear optimization. Therefore, the resulting optimization problem is polynomially solvable.

In the following, we review alternative routing sets F that are less restrictive than static routings while not being as flexible as dynamic routings i.e., F stat ⊆ F ⊆ F .

Static routing with hyperplane coverage

Given a set D, a collection of subsets of D forms a cover of D if D is a subset of the union of sets in the collection. Ben-Ameur [3] introduces the idea of covering the uncertainty set by two (or more) subsets using hyperplanes and proposes to use a routing template for each subset. This yields the following set of routings:

F 2| ≡ f ∈ (D, R |A|×|K| ) | ∃y 1 , y 2 ∈ Y and α ∈ R K , β ∈ R : f k a (d) = y 1k a d k d ∈ D ∩ {d, αd ≤ β} y 2k a d k d ∈ D ∩ {d, αd ≥ β} a ∈ A, k ∈ K, d ∈ D .
The definition above implies that both routing templates y 1 and y 2 must be able to route demand vectors that lie in the hyperplane {d, αd = β}. The authors prove that RN D(F 2| ) is N P-hard in general and describes simplification schemes, where α is given. He further works on the framework in [START_REF] Ben-Ameur | Robust routing and optimal partitioning of a traffic demand polytope[END_REF].

Static routing with unrestricted 2-coverage

Scutellá [START_REF] Scutellà | On improving optimal oblivious routing[END_REF] introduces the idea of using conjointly two routing templates. Formally, she proposes to use two routing templates y 1 and y 2 such that each d ∈ D can be served either by y 1 or by y 2 (or both). This yields the set of routings

F 2 ≡ f ∈ (D, R |A|×|K| ) |∃y 1 , y 2 ∈ Y and D 1 , D 2 ⊆ D, D = D 1 ∪ D 2 : f k a (d) = y 1k a d k d ∈ D 1 y 2k a d k d ∈ D 2 a ∈ A, k ∈ K, d ∈ D .
She uses a technical proof to show that RN D(F 2 ) is N P-hard in [START_REF] Scutellà | Hardness of some optimal oblivious routing generalizations[END_REF]. We provide a simpler proof in this paper, based on the fact that RN D(F 2 ) is a generalization of RN D(F 2| ), proved to be N P-hard by [3]. The framework described by F 2 has been independently proposed for general robust programs by [START_REF] Bertsimas | Finite adaptability in multistage linear optimization[END_REF] where the authors propose to cover the uncertainty sets with k subsets and devise independent sets of recourse variables for each of these subsets.

Volume routings

More recently, [START_REF] Ben-Ameur | Volume oriented routing[END_REF] introduce a framework that shares the demand between two routing templates, according to thresholds h k for each k ∈ K. Namely, for each k ∈ K, any volume routing sends min(d k , h k ) along the first routing template while max(d k -h k , 0) is sent along the second routing template:

F V ≡ f ∈ (D, R |A|×|K| ) |∃y 1 , y 2 ∈ Y, h ∈ R K + : f k a (d) = y 1k a min(d k , h k ) + y 2k a max(d k -h k , 0) a ∈ A, k ∈ K, d ∈ D} .
They prove that RN D(F V ) is an N P-hard optimization problem. To make the problem more computationally tractable, they introduce simpler frameworks described below. The first simplification (F VS ) supposes that for each commodity, the threshold is equal to the minimal value of the demand over the uncertainty set. Defining d k min = min d∈D d k , any routing in F VS sends d k min along the first routing template while d k -d k min is sent along the second routing template:

F VS ≡ f ∈ (D, R |A|×|K| ) | ∃y 1 , y 2 ∈ Y : f k a (d) = y 1k a d k min + y 2k a (d k -d k min ) a ∈ A, k ∈ K, d ∈ D .
Their third routing set (F VG ) also considers pairs of routing templates but without thresholds. Defining d k max = max d∈D d k , any routing in F VG sends d k min along the first routing template and d k max along the second routing template. Then, for any

demand d k = λd k min + (1 -λ)d k max with 0 ≤ λ ≤ 1
, the routing sends λd k min along the first routing template and (1 -λ)d k max along the second routing template:

F VG ≡ f ∈ (D, R |A|×|K| ) | ∃y 1 , y 2 ∈ Y : f k a (d) = y 1k a d k min d k max -d k d k max -d k min + y 2k a d k max d k -d k min d k max -d k min a ∈ A, k ∈ K, d ∈ D} , which is well-defined whenever d k min < d k max for each k ∈ K. When d k min = d k max for some k ∈ K, the k-th component of f ∈ F VG is defined by f k (d) = y 1k d k .

Affine routings

Ben-Tal et al. [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF] introduce Affine Adjustable Robust Counterparts restricting the recourse to be an affine function of the uncertainties. Ouorou and Vial [START_REF] Ouorou | A model for robust capacity planning for telecommunications networks under demand uncertainty[END_REF] apply this framework to robust network design by restricting f k to be an affine function of all components of d giving

F aff ≡ f ∈ (D, R |A|×|K| )|∃f 0 ∈ R K , y ∈ R |A|×|K| : f k a (d) = f 0k a + h∈K y kh a d h a ∈ A, k ∈ K, d ∈ D, (2) and (3) .
This framework has been compared theoretically and numerically to static and dynamic routings by [START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF]. In particular, the authors show that a compact formulation can be described for RN D(F aff ) as long as D has a compact description, generalizing the result obtained for static routing already. We point out that a major difference between F aff and the routing described in Section 2.2.1-2.2.4 is that the former is built up using routing templates, so that it is implicitly assumed that flow conservation constraints (2) and non-negativity constraints (3) are satisfied. Conversely, routings in F aff are built up using ordinary vectors so that that satisfaction of (2) and (3) must be stated explicitly.

Optimal costs

The objective of this section is to compare the cost of the optimal capacity allocations obtained for RN D(F ) by using different routing sets F . More specifically, we compare F 2| with F 2 , F aff with F VS and F VG , and F VS with F V . Our main results are stated next.

(a) Let D be an uncertainty set. It holds that opt(F 2 ) ≤ opt(F 2| ) and opt(F aff ) ≤ opt(F VG ) ≤ opt(F VS ). (b) Let D be an uncertainty polytope such that for each k ∈ K, there exists nonnegative numbers 0

≤ d k min ≤ d k max such that d k ∈ {d k min , d k max } for each extreme point of D. It holds that opt(F V ) = opt(F VS ).
The polytope introduced by [START_REF] Bertsimas | The Price of Robustness[END_REF], used for robust network design problems in [START_REF] Ben-Ameur | Volume oriented routing[END_REF][START_REF] Ouorou | A model for robust capacity planning for telecommunications networks under demand uncertainty[END_REF][START_REF] Koster | Robust network design: Formulations, valid inequalities, and computations[END_REF][START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF], satisfies the assumption of (b) when the number of deviations allowed is integer. We present examples in Section 4 showing that it is not possible, in general, to order opt(F 2 ), opt(F V ) and opt(F aff ).

Given two routing sets F and F * , we prove that opt(F ) ≤ opt(F * ) using two different approaches. The first approach consists in comparing directly the routing sets themselves, by showing that F * ⊆ F . The second approach is based on comparing the sets of all capacity allocations that support D when considering a specific routing set. These sets are defined formally as

X (F ) ≡ {x ∈ R |A| + | (x, F ) supports D}, (10)
for any routing set F . To better understand the link between X (F ) and opt(F ), RN D(F ) can be equivalently written as min a∈A κ a x a s.t. x ∈ X (F ) . The two approaches are formalized in the proposition below stated without proof.

Proposition 1 Let F and F * be two routing sets.

If F * ⊆ F or X (F * ) ⊆ X (F ), then opt(F ) ≤ opt(F * ).
In the following, we will use Proposition 1 to relate the optimal capacity allocation costs among the routing sets introduced in Section 2.2.

Proposition 2 Let D be an uncertainty set. It holds that X (F 2| ) ⊆ X (F 2 ).

Proof The results directly follows from the fact that F 2| is the subset of F 2 where the intersection of D 1 and D 2 must be a hyperplane.

The complexity of RN D(F 2 ) follows directly from the sufficiency condition of Proposition 2 and the fact that [3] proves RN D(F 2| ) to be N P-hard, thus providing a simpler proof than [START_REF] Scutellà | Hardness of some optimal oblivious routing generalizations[END_REF].

Corollary 1 The optimization problem RN D(F 2 ) is N P-hard.
In what follows, we compare volume and affine routings. Ben-Ameur and Zotkiewicz [START_REF] Ben-Ameur | Volume oriented routing[END_REF] mention that F VS is a special case of F V , that is, F VS ⊆ F V . The inclusion is easily verified for F VS , by choosing h k = d k min .

Lemma 1 [START_REF] Ben-Ameur | Volume oriented routing[END_REF] It holds that

F VS ⊆ F V .
However, it is not true that F VG ⊆ F V for the following reason. Any routing in F V is a non-decreasing functions of d. In opposition, any routing in F VG is the sum of a non-increasing function of d and a non-decreasing function of d. The advantage of decreasing the flow sent on some arcs when the demand for a commodity rises allows to better combine different commodities within the available capacity. We provide in Section 4.2 an example showing that, in general, it holds that F VG F V . Routing sets F VS or F VG are nevertheless special cases of affine routings. Because any routing in F VS or F VG is described by an affine functions of d, it must also belong to F aff . The result below shows, moreover, that F VS is a special case of F VG .

Proposition 3 Let D be an uncertainty set. The following holds: < 0 for some a ∈ A and k ∈ K. 2. Suppose that dim(D) = 1 and that D is not orthogonal to any of the coordinate axes, and consider any routing f ∈ F aff and a commodity k ∈ K. We can parameterize D through its orthogonal projection on the k-th axis. Denoting these projections by λ h ∈ R + for each h ∈ K\k, the flow for k is given by

1. F VS ⊆ F VG .
f 0k a +   y kk a + h∈K\k λ h y kh a   d k = f 0k a + y kk a d k . ( 11
)
The flow from ( 11) is equal to the flow prescribed by a routing f ∈ F VG described by routing templates

y 1k = f 0k a /d k min + y kk a and y 2k = f 0k a /d k max + y kk a for each a ∈ A and k ∈ K.
Suppose that either dim(D) > 1 or dim(D) = 1 and D is orthogonal to one of the coordinate axis. Then, there exists a pair {d 1 , d 2 } ⊂ D such that

d k 1 = d k 2 and d h 1 = d h 2 for some k, h ∈ K.
Hence, all routings in F VG for commodity k yield identical flows for d 1 and d 2 , while we can define an affine routing f ∈ F aff yielding different flows by choosing a proper y kh = 0.

Ben-Ameur and Zotkiewicz [START_REF] Ben-Ameur | Volume oriented routing[END_REF] have provided instances for which the relation opt(F VG ) < opt(F VS ) holds. Thus, for these instances, the strict inclusion of Proposition 3.1 holds as well.

We show next that F VS is always at least as efficient as F V whenever D satisfies the assumption below. Given a convex set D ⊂ R |K| + , we denote by ext(D) the set of its extreme points. Example 1 Bertsimas and Sim [START_REF] Bertsimas | The Price of Robustness[END_REF] consider general linear programs where the coefficients of each linear inequality belong to intervals such that the number of coefficients taking conjointly their maximum value is bounded by a constant Γ .

Considering upwards deviations only, their uncertainty set can be formalized in

R |K| + as follows D Γ ≡ d ∈ R |K| + | d k ∈ [d k min , d k max ] for each k ∈ K, k∈K d k -d k min d k max -d k min ≤ Γ .
(12) When Γ is integer, it is easy to see that D Γ fulfills Assumption 1. Moreover, D Γ has been frequently used as the uncertainty set for robust network design problems, see [START_REF] Ben-Ameur | Volume oriented routing[END_REF][START_REF] Ouorou | A model for robust capacity planning for telecommunications networks under demand uncertainty[END_REF][START_REF] Koster | Robust network design: Formulations, valid inequalities, and computations[END_REF][START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF], among others.

The proof of the next result requires the following simple property. For any

x ∈ R |A| + and f ∈ F VS , (x, f ) supports D ⇔ (x, f ) supports ext(D). ( 13
)
Property ( 13) follows directly from the fact that any routing in F VS is a linear function.

Proposition 4 Let D be an uncertainty set that fulfills Assumption 1. It holds that

X (F VS ) = X (F V ).
Proof We prove X (F V ) ⊆ X (F VS ) since it is already clear that X (F VS ) ⊆ X (F V ) holds. Consider a capacity allocation x and a routing f ∈ F V such that (x, f ) supports D. Because of Property ( 13), it is enough to show that there exists a routing f ∈ F VS such that f (d) = f (d) only for each d ∈ ext(D). If d k min = 0, all routings are equal at that extreme point. Hence, we can suppose that d k min > 0. After simple computations, we see that the flow templates given by y 1k a =

f k a (d k min )/d k min and y 2k a = (f k a (d k max ) -f k a (d k min ))/(d k max -d k min )
for each a ∈ A and k ∈ K describe the required routing f . Proposition 4 states that whenever D satisfies Assumption 1, one should not try to use the complex set of routings F V , since opt(F V ) will never beat opt(F VS ). This is of particular interest because RN D(F V ) is N P-hard in general while [START_REF] Ben-Ameur | Volume oriented routing[END_REF] show that RN D(F VS ) is essentially of the same difficulty as RN D(F stat ).

Non-comparable routings

In this section, we compare opt(F 2 ), opt(F V ) and opt(F aff ) for general uncertainty sets. We show that it is not possible to order these costs by presenting three examples where one of the costs is strictly less than the two others. To devise examples showing that F aff may yield more expensive capacity allocations than F 2 and F V , we shall use the following result. Let e k be the k-th unit vector in

R |K| + . Proposition 5 [23, Proposition 8] Let D be a demand polytope. If 0 ∈ D and for each k ∈ K there is k > 0 such that k e k ∈ D, then opt(F aff ) = opt(F stat ).
Notice that in our examples some of the commodities have unique paths from their sources to their sinks, so that all routings are equal for these commodities. This enables us to produce simple graphs that present the properties required by our examples. One can easily extend these examples to larger graphs for which each commodity k ∈ K has at least two different paths from its source s(k) to its sink t(k). Fig. 1 Example showing that opt(F V ) can can be strictly smaller than opt(F aff ) and opt(F 2 ).

4.1 opt(F V ) can be strictly smaller than opt(F aff ) and opt(F 2 )

Consider the network design problem for the graph depicted in Figure 1(a) with two commodities k 1 : a → c and k 2 : a → b. The uncertainty set D is defined by the extreme points

d 1 = (2, 1), d 2 = (1, 2), d 3 = (1, 0), d 4 = (0, 1)
, and d 5 = (0, 0), and the capacity unitary costs are the edge labels of Figure 1(a). Edge labels from Figure 1(b) and Figure 1(c) represent optimal capacity allocations with dynamic and static routing, respectively. They have costs of 7 and 8, respectively. A routing f ∈ F that satisfies the capacity from Figure 1(b) is depicted on Figure 1(d) and Figure 1(e), for d 1 and d 2 , respectively. We show next that the optimal capacity allocations for F V , F 2 , and F aff are 7, 8 and 8, respectively. The routing f from Figure 1(d) and Figure 1(e) can be extended to a routing in f ∈ F V such that (x, f ) supports D by fixing

h k1 = 1, h k2 = 2, y 1k1 = f k1 (d 2 ), y 2k1 = f k1 (d 1 ) -f k1 (d 2 ),
and

y 1k2 = y 2k2 = f k2 (d 1 )
.

However, we explain next why it cannot be extended to a routing in F 2 within the capacity x from Figure 1(b). We restrict our attention to the subset of D that consists of the line segment D = conv(d 1 , d 2 ) and show that f can already not be extended to a routing in F 2 for D . Consider flow f (d 1 ) depicted in Figure 1(d). This flow uses the routing template y 1 defined as

y 1k = f k (d k 1 )/d k 1 for k = k 1 , k 2 . Similarly, flow f (d 2 ) uses the routing template y 2k = f k (d k 2 )/d k 2 for k = k 1 , k 2 .
Then, we see that d 1 (resp. d 2 ) is the unique demand vector in D that can be routed within the capacity x from Figure 1(b) using routing template y 1 (resp. y 2 ). Therefore, defining D 1 (resp. D 2 ) as the subset of D that contains all demand vectors that can be routed along routing template y 1 (resp. y 2 ), we have that D 1 ∪ D 2 ⊂ D . This shows that it is not possible to extend f to a routing in F 2 for D , so that it is not possible to do so for D either.

In fact, we have that the optimal capacity allocation for F 2 is obtained when D is covered only by itself, yielding opt(F 2 ) = 8. For F aff , we can apply Proposition 5 (because {(0, 0), (1, 0), (0, 1)} ⊂ D) so that opt(F aff ) = opt(F stat ) = 8. and f k2 ac (d 2 ) < f k2 ac (d 1 ), that is, f is not a non-decreasing function. We can show in addition that, using a reasoning similar to the one used in the previous section, f cannot be extended to a routing in F 2 within the existing capacity. We can see that an optimal capacity allocation using F V or F 2 is also an optimal capacity allocation using F stat , and it requires two more units of capacity on ab and no capacity on cd, see Figure 2(c), which yields a total cost of 26.

4.3 opt(F 2 ) can be strictly smaller than opt(F aff ) and opt(F V ) Consider the network design problem for the graph depicted in Figure 3 and f k2 ac (d 2 ) < f k2 ac (d 1 ), that is, f is not a non-decreasing function. In fact, we have that opt(F V ) = opt(F stat ) = 9. Then, we can apply Proposition 5 (because {(1, 0, 0), (0, 1, 0), (0, 0, 1), (0, 0, 0)} ⊂ D) to the problem with F aff , so that opt(F aff ) = opt(F stat ) = 9.

Computational experiments

We report in this section on computational experiments realized for the routing sets that yield polynomially solvable optimization problems: F stat , F aff , F VS , and F VG . The experiments have been carried out on a computer equipped with a processor Intel Core i7 at 2.90 GHz and 8 GB of RAM memory allowing for 3 threads, and the linear programs were solved by CPLEX 12.4 [17].

The experiments were based on the uncertainty set D Γ defined in [START_REF] Chekuri | Hardness of robust network design[END_REF], for various values of Γ , and they were realized on three networks from SNDlib [START_REF] Orlowski | SNDlib 1.0-Survivable Network Design Library[END_REF], janos-us, sun, and giul39. These networks are feasible for a directed formulation and have 26/27/39 nodes and 84/102/172 arcs, respectively. We considered the largest 10 to 50 commodities k with respect to nominal demand value, which allowed us to perform a series of runs for each network. For each k ∈ K, we followed [START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF] and set d k min to the nominal demand value and d k max to 1.4d k min . The results from Table 1 were obtained by solving the compact linear programming formulation obtained when dualizing the robust constraints in RN D(F ) for each considered routing set, see for instance [START_REF] Altin | Provisioning virtual private networks under traffic uncertainty[END_REF][START_REF] Ouorou | A model for robust capacity planning for telecommunications networks under demand uncertainty[END_REF][START_REF] Poss | Affine recourse for the robust network design problem: between static and dynamic routing[END_REF] for details. Columns "Cost" compare the optimal solution cost of each routing F with the cost provided by F stat . Namely, we report 100(1 -opt(F )/opt(F stat )) for each considered F . Columns "Time" report solution times in seconds for solving each instance with the barrier solver of CPLEX. We switched off the crossover of CPLEX because our aim is to compute the optimal objective values.

Our experiments show that the two simplified volume routings always yield the same optimal solution costs. This is not surprising because [START_REF] Ben-Ameur | Volume oriented routing[END_REF] had observed the same situation happening in most of their experiments. We see then that, for many instances, these routings yield optimal solution costs very close to the solution costs provided by affine routing. Moreover, their solution times are order of magnitude smaller than those of affine routings, thus providing an interesting alternative to affine routing when the available computing time is limited.

Concluding remarks

This paper studies the optimal capacity allocation cost provided by robust network design models restricted to use specific routing sets. These routing sets are: affine routing, volume routing and its two simplifications, and the routings based on covers of the demand uncertainty set. We show that the simplified volume routings are special cases of affine routings and study when the inclusions are strict. We show then that the general volume routing is no more flexible than its simplifications whenever the uncertainty set is the polytope introduced by Bertsimas and Sim. We complete our comparison by examples and a computational study of some of these routings.

An important characteristic of these routing sets is the complexity of the resulting network design problem. In this respect, the general volume routings and the routing sets based on covers of the uncertainty set lead to N P-hard optimization problems. Moreover, while a finite linear programming formulation can be provided for the robust network design problem with dynamic routing under polyhedral uncertainty (by considering only the extreme points of the demand polytope), no such formulations are known for the problems that use the general volume routings or the routings based on covers of the uncertainty set. In this sense, these two routing sets yield optimization problems that are computationally even more difficult than the robust network design with dynamic routing. In opposition, affine routing and the two simplified volume routings lead to polynomially solvable optimization problems, given that the uncertainty polytope has a compact description.

Assumption 1

 1 The uncertainty set D is a polytope such that for each k ∈ K, d k ∈ {d k min , d k max } for all d ∈ ext(D) where d k min and d k max are defined above (and exist).

Assumption 1

 1 is satisfied by a well-known family of uncertainty polytopes, see Example 1.

  (a) edge costs (b) optimal capacity allocation with F V (c) optimal capacity allocation with F 2 or F aff (d) f (d 1 ) (e) f (d 2 )

Fig. 2

 2 Fig.2Example showing that opt(F VG ) (thus opt(F aff )) can can be strictly smaller than opt(F V ) and opt(F 2 ).

4. 2

 2 opt(F VG ) and opt(F aff ) can be strictly smaller than opt(F V ) and opt(F 2 ) Consider the network design problem for the graph depicted in Figure2(a) with three commodities k 1 : a → b, k 2 : a → d and k 3 : a → e. The uncertainty set D is defined by the extreme points d 1 = (3, 2, 0) and d 2 = (0, 3, 2), and the capacity unitary costs are the edge labels of Figure 2(a). Edge labels from Figure 2(b) represent an optimal capacity allocation for dynamic routing, with cost 22. A routing f ∈ F that satisfies the capacity from Figure 2(b) is depicted on Figure 2(d) and Figure 2(e), for d 1 and d 2 , respectively. This routing can be extended to a routing f ∈ F VG such that (x, f ) supports D by setting y 1k1 = y 2k1 = f k1 (d 1 )/3, y 1k2 = f k2 (d 1 )/2, y 2k2 = f k2 (d 2 )/3 and y 1k3 = y 2k3 = f k3 (d 2 )/2. Applying Proposition 3.2., f also belongs to F aff . However, f cannot be extended to a routing in F V already because d k2 2 > d k2 1

Fig. 3

 3 Fig.3Example showing that opt(F 2 ) can can be strictly smaller than opt(F aff ) and opt(F V ).

  The inclusion is strict if and only if there exists k ∈ K such that The inclusion F VG ⊂ F aff holds if and only if dim(D) > 1 or dim(D) = 1 and D is orthogonal to one of the coordinate axes of R If d max = 0 or d k min = d k max for some commodity k ∈ K, then routings in F VS and F VG coincide for that commodity. Hence, we suppose in what follows that 0 < d k min < d k max for each k ∈ K. Let the routing templates y 1 and y 2 describe any routing f ∈ F VS . Then, routing templates y 1k a = y 1k a and y 2k a = ∈ A and k ∈ K describe a routing f ∈ F VG equal to f . Conversely, given a routing f ∈ F VG described by routing templates y 1 and y 2 , the equivalent routing f ∈ F VS is described by routing templates y 1k a = y 1k

	2. |K| + .
	y 1k a	d k min d k max	+ y 2k a	d k max -d k min d k max	for each a a
	and y 2k a = y 2k a -y 1k a	d k min max d k	for each a ∈ A and k ∈ K. Hence, the strict inclusion is
	verified by choosing a routing f ∈ F VG such that y 2k a -y 1k a	d k min d k max
		0 < d k min < d k max .

Proof 1.

Table 1

 1 Numerical results. 2. D. Applegate and E. Cohen. Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs. In Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, SIGCOMM '03, pages 313-324. ACM, 2003. 3. W. Ben-Ameur. Between fully dynamic routing and robust stable routing. In 6th International Workshop on Design and Reliable Communication Networks, 2007. DRCN 2007, 2007. 4. W. Ben-Ameur and H. Kerivin. New economical virtual private networks. Communications of the ACM, 46(6):69-73, 2003.

	Instances			Cost			Time
		|K|	Γ	F VS	F VG	F aff	F stat	F VS	F VG	F aff
		10	1	5.8	5.8	5.8	0.03	0.06 0.06	3.73
		10	2	0	0	0	0.02	0.05 0.08	1.87
		20	1	7.2	7.2	7.2	0.09	0.14 0.31	43.7
		20	2	6.2	6.2	6.2	0.11	0.17 0.31	64.2
		20	3	0.9	0.9	0.9	0.06	0.19 0.27	51.2
		30	1	7.5	7.5	7.5	0.2	0.37 0.67	160
		30	3	6.6	6.6	6.6	0.16	0.42 0.72	179
	janos-us	30	5	0	0	0	0.12	0.34 0.72	175
		40	1	8.2	8.2	8.2	0.11	0.61 0.37	528
		40	4	2.9	2.9	2.9	0.08	0.75 0.47	723
		40	6	0	0	0	0.08	0.62 0.33	345
		50	1	8.4	8.4	8.4	0.11	0.95 0.55 1933
		50	3	7.2	7.2	7.3	0.11	1.05 0.66 2010
		50	5	2	2	2.1	0.11	1.08 0.75 3439
		50	7	0	0	0	0.11	0.98	0.5	1360
		10	1	8.7	8.7	9.8	0.03	0.06 0.08	1.59
		10	2	1.1	1.1	2.7	0.03	0.08 0.08	1.7
		20	1	8.9	8.9	9.9	0.08	0.14 0.33	25.9
		20	2	8	8	8.9	0.08	0.14 0.31	27.9
		20	3	4.4	4.4	6.3	0.08	0.17 0.34	44.6
		30	1	7.9	7.9	9.2	0.16	0.45 0.76	135
		30	3	6.6	6.6	8.8	0.14	0.44 0.86	146
	sun	30	5	1.7	1.7	2.2	0.14	0.44	0.7	132
		40	1	7.7	7.7	8.5	0.16	0.69 1.31	542
		40	4	6.8	6.8	8.8	0.19	0.72 1.28	563
		40	6	2.8	2.8	4.6	0.16	0.76	1.2	645
		50	1	7	7	8	0.2	1.14 0.34 1956
		50	3	8.6	8.6	10.4	0.25	1.25 0.37 1868
		50	5	6.5	6.5	8.6	0.27	1.29 0.41 1861
		50	7	3.8	3.8	6.2	0.23	1.29 0.33 1691
		10	1	2.6	2.6	2.6	0.05	0.08 0.09	3.6
		10	2	1	1	2.3	0.05	0.11 0.11	3.46
		20	1	4.1	4.1	4.2	0.14	0.39 0.41	62.7
		20	2	5.5	5.5	5.8	0.14	0.41 0.42	65.2
		20	3	4.5	4.5	4.9	0.14	0.36 0.55	65.1
		30	1	7.8	7.8	8.1	0.28	0.72 1.12	422
		30	3	7.4	7.4	8.0	0.25	0.86 1.25	466
	giul39	30	5	4	4	5.1	0.27	0.78 1.17	491
		40	1	8.8	8.8	9.2	0.47	1.34 2.03 1292
		40	4	6.8	6.8	7.5	0.45	1.45 2.15 1385
		40	6	3.7	3.7	4.9	0.47	1.37	2	1379
		50	1	8.2	8.2	8.6	0.48	2	3.17 4601
		50	3	9.6	9.6	10.6	0.55	2.23 3.18 4573
		50	5	7.2	7.2	8.1	0.53	2.23 3.48 4377
		50	7	4.2	4.2	5	0.5	2.03 3.65 3774

Acknowledgements

The author is grateful to Christian Raack and to a referee for numerous comments that helped in improving the presentation of the paper.