Asya Achimova

Christa Crosby

Kristen Syrett

Viviane Déprez

Julien Musolino

Which account of wh-/quantifier interaction Should everyone adopt? A new take on a classic developmental puzzle

Introduction *

Quantifiers are expressions that denote number and quantity [START_REF] Peters | Quantifiers in language and logic[END_REF]. When quantifiers interact with each other or with other logical expressions in a sentence, the resulting interpretation may be ambiguous (cf. May 1985, a.o.). In this paper, we focus on young chilren's understanding of the interaction of the universal quantifiers every and each with wh-expressions (who, which) in questions such as (1).

(1)

Which game did every friend play t? a. Every friend played Candy land. b. Woody played Candy Land, Jessie played Sorry, and Buzz played Monopoly.

In (1), the quantifier phrase every friend is in subject position and the underlined wh-expression has moved to the front of the sentence. This question allows for at least two types of answers: a single answer (1a) and a pair-list answer (PLA) (1b). Questions such as (2), where the quantifier phrase is in object position, are claimed to only allow a single answer and not a PLA. (Compare (2a) to (2b).)

(2) Which friend t played every game? a. Jessie played every game.

* Rutgers University. Contact author: Asya Achimova, achimova@rutgers.edu.

We would like to thank Max Kon for creative ideas on stimuli design, Paul de Lacy and the Rutgers Phonology Lab for their help in stimuli recording, the Aresty Research Center at Rutgers for their funding, and our preschools friends for their essential contributions.

*b. Woody played Candy Land, Jessie played Sorry, and Buzz played Monopoly.

Several analyses have been proposed to account for this subject-object asymmetry. [START_REF] Robert | Logical form: its structure and derivation[END_REF][START_REF] May | Ambiguities of 1uantification and wh: a reply to Williams[END_REF] characterized the ambiguity of answers in (1) as a scopal ambiguity. A single answer is derived when the wh-phrase takes scope over the quantifier. For a PLA, the quantifier must scope over the wh-phrase, reversing the order of these elements in Logical Form. (See Chierchia (1993) and Szabolcsi (1997) for accounts that do not rely on scope.) [START_REF] Beghelli | The syntax of distributivity and pair-list readings[END_REF][START_REF] Chierchia | Questions with quantifiers[END_REF], [START_REF] Agüero-Bautista | Cyclicity and the scope of wh-phrases[END_REF] have also emphasized the importance of quantifier type (every/each) and the wh-phrase (who/which) in the availability of a PLA. In light of the complexity of this phenomenon, sentences with wh-/quantifier interactions may pose a challenge for preschoolers.

Indeed, [START_REF] Roeper | The Emergence of bound variable structures[END_REF] observed that while children 3 to 5 years of age are capable of producing PLAs for subject-quantifier questions like (1), they appear to overgeneralize PLAs for object quantifier questions like (2). These results suggested that preschoolers have yet to acquire the necessary linguistic operations governing question-quantifier subject-object asymmetries. [START_REF] Yamakoshi | The acquisition of wh/every interaction in English[END_REF] later questioned these findings, citing oversights in experimental design. However, neither of these studies took into account the above lexical distinctions. As a result, the current literature paints an incomplete picture of what children know about the range of possible answers to questionquantifier interactions. In this paper, we restrict our attention to which-phrases, which are predicted under all accounts to induce a subject-object asymmetry in interactions with the quantifier every, as in (1). By doing so, we demonstrate that children do produce significantly more PLAs in questions with object quantifier every than adults. Second, by carefully controlling for quantifier type and wh-phrases, we illustrate that the development of this linguistic phenomenon is more complex than originally observed.

In the next section, we review the key previous studies on this topic. In Section 3, we offer a brief theoretical overview of the factors influencing the availability of PLAs. Sections 4 and 5 present our research design and experimental findings. We conclude with a general discussion in Section 6.

Production and availability of pair-list answers

stories like the one in (3). These were followed by subject or object questions such as (4) or (5). In this example, the picture showed the sister pulling the boy, the Daddy pulling the sister, and the horse pulling the dad.

(3)

A little boy got stuck in the mud. He called his sister for help. She tried pulling him, but was unable to get him out. Then they called Daddy, who could not help either. Finally, a horse came and pulled the Daddy, and look, out came the boy! (4) Who did everyone pull? (5)

Who pulled everyone?

The subject quantifier question in (4) has two possible answers: either that everyone pulled the boy (a single answer), or a list of the puller-pullee pairings (a PLA). The percentage of answers reported by Roeper & de Villiers is presented in Table 1. Children allowed single answers, as expected, but preferred PLAs for both question typeseven for questions with object quantifiers like (5), where PLA should be unavailable. This pattern of overgeneralization led Roeper & de Villiers to conclude that children are insensitive to the attested subject-object asymmetry and therefore have an immature grammar. [START_REF] Yamakoshi | The acquisition of wh/every interaction in English[END_REF] later attempted to replicate these results, but included a twist by asking children whether they thought the horse also pulled the boy. 73.8% of the children replied 'no', presumably indicating that they did not recognize that the horse indirectly pulled everyone, even though it only directly pulled the father. Yamakoshi reasoned that they were therefore unable to access the single answer and only had the PLA as an option. Yamakoshi's experiment avoided this pitfall, and rate of PLAs were lower in object-quantifier than in subjectquantifier questions. See Table 2. Yamakoshi concluded that although children age four and five may prefer PLAs when given the option, they do not overgeneralize PLAs. The picture, however, is not so black and white. First, [START_REF] Yamakoshi | The acquisition of wh/every interaction in English[END_REF] employed a conservative method of tallying PLAs. A partial answer or one that only listed one member of a pair was not counted as a PLA, and was instead classified as 'other'. In our experiments, we found that children often provided such partial answers in response. For example, when asked Which game did every friend play? children would answer, Candy Land, Sorry, and Monopoly. Moreover, some children did not respond verbally, instead pointing to items on the screen. If we return to Yamakoshi's study and count such answers as PLAs (since they are clearly not single answers, and indicate a character-object mapping as in a PLA), we obtain a much higher rate of PLAs, as indicated in the percentages in parentheses in Table 2.

In the next section, we briefly present theoretical accounts stating that PLAs are typically barred in such object-quantifier questions. However, we also review arguments that the choice of wh-phrase and universal quantifier influence the presence of the subject-object asymmetry. Neither of the previous studies systematically controlled for either type of lexical item-a factor that appears to be of no small consequence.

The availability of pair-list answers with object quantifier questions

In this section we briefly review the major theoretical accounts of the subject-object asymmetry in wh-/quantifier interaction. According to [START_REF] Robert | Logical form: its structure and derivation[END_REF][START_REF] May | Ambiguities of 1uantification and wh: a reply to Williams[END_REF], a PLA is possible with a subject-quantifier question, but it is blocked for object-quantifier questions, because the movement path of the whphrase to its surface position in the Specifier of CP and of the quantifier phrase undergoing Quantifier Raising (QR) would have to cross. Alternative accounts of the subject-object asymmetry have appealed to a Weak Crossover constraint [START_REF] Chierchia | Questions with quantifiers[END_REF] or restrictions on reconstruction of the wh-phrase to its base position [START_REF] Beghelli | The syntax of distributivity and pair-list readings[END_REF][START_REF] Agüero-Bautista | Cyclicity and the scope of wh-phrases[END_REF][START_REF] Agüero-Bautista | Diagnosing cyclicity in sluicing[END_REF]. PLAs require the whphrase to reconstruct below the quantifier. Both [START_REF] Chierchia | Questions with quantifiers[END_REF] and [START_REF] Agüero-Bautista | Cyclicity and the scope of wh-phrases[END_REF], albeit for different reasons, note that questions with who-phrases can sometimes give rise to PLA, even when the quantifier is in object position. However, [START_REF] Agüero-Bautista | Cyclicity and the scope of wh-phrases[END_REF] argued that presuppositional whphrases, such as which-phrases, cannot reconstruct into the position from which they originated. Thus, the object quantifier is prevented from taking scope over the wh-phrase. For subject-quantifier questions, a position is available for reconstruction below the quantifier but outside of the VP where the wh-phrase originated, allowing PLAs. By using questions with who, Roeper & de Villiers (1991) introduced a possible confound: the rather high production rate for PLAs in response to object-quantifier questions could have been due in part to the choice of lexical item.

Likewise, the choice of quantifier matters. [START_REF] Beghelli | The syntax of distributivity and pair-list readings[END_REF] pointed out that not all universal quantifiers display the same behavior in questions. While questions with every in object position appear not to allow PLAs, questions with each in object position do. See ( 6). ( 6) Q: Which friend played each game? A: Woody played Candy Land, Jessie played Sorry, and Buzz played Monopoly.

According to Beghelli, in the process of Quantifier Raising, each takes a position higher in the syntactic tree than every, landing in the Specifier of a Distributive Phrase (a projection he proposes is situated above the IP node). As a result, each can take scope over the subject wh-phrase at LF, and a PLA becomes available. The quantifier every stays within IP [START_REF] Beghelli | The syntax of distributivity and pair-list readings[END_REF][START_REF] Beghelli | Distributivity and negation[END_REF], Szabocsi 1997), a position too low to take scope over the reconstructed wh-term. This difference in syntactic behavior is related to a semantic difference in the distributivity requirements of these two quantifiers, in that each has a stronger event distributivity requirement than every (Tunstall,1998).

Concerns with previous experimental methodology and the role of lexical items led us to revisit children's comprehension of wh-/quantifier questions and the question of whether they actually do overgeneralize PLAs. We were also interested in obtaining an adult baseline related to the above theoretical claims. Specifically, we sought to determine (a) the rate of PLAs for both age groups in response to subject-and object-quantifier questions involving which (to ascertain the presence of a subject-object asymmetry) and (b) whether this pattern is sensitive to quantifier type (each vs. every).

Methods

Participants. 32 children (16 four-year-olds, mean: 4.6, range: 4.0-4.9 and 16 five-years-old, mean: 5.2; range: 5.0-5.4 y.o.) and a control group of Rutgers undergraduates (n = 28) participated. Three children who did not successfully complete the practice trials were excluded from the analysis.

Design and procedure. We employed a 2x2 design: syntactic position of the quantifier (subject vs. object) was manipulated within subjects, while quantifier type (each vs. every) was between subjects. The wh-word was always which. The experiment began with a 2-item practice session, which was followed by an experimental session consisting of 12 items (6 critical and 6 control trials). Control trials aimed at testing whether children understand questions without quantifiers, are able to produce PLA and single answers in general, as well as whether children treat every and each as universal quantifiers.

Participants were tested individually. They were presented with a story animated on a computer monitor and narrated by the experimenter. For adults, the narration and question were pre-recorded; for children, these were presented live by a female native speaker of English. The story was followed by a wh-/quantifier question. Each story had the same template. There were three characters and three objects. All of the characters first interacted with one of the objects. Then two of the characters interacted with another object. The narrative and question from a sample story is presented in (7), accompanied by the onscreen display in Figure 1. (7) Buzz, Jesse, and Woody decided to play board games. They played Candy Land first. But then Buzz wanted to play another game, so he played Monopoly. Jesse also wanted to play another game, and so she played Sorry. Which game did every friend play?

Figure 1. Subject-quantifier story

The single answer, in which the wh-phrase takes scope over the quantifier, should be Candy Land. The PLA, derived from the quantifier taking scope over the wh-phrase, should be Woody played Candy Land, Jesse played Sorry, and Buzz played Monopoly. For each story, we used verbal cues and visual aids, such as footprints in this example, to make both readings salient. The example in ( 8) and the scene in Figure 2 accompanied an objectquantifier question. Here, only the single answer should be available. We predicted that participants who are aware of the constraints associated with the type and position of the quantifier should provide the single answer Jasmine. If, however, child participants overgeneralize PLAs (and if adults allow the quantifier to take scope over the wh-phrase), they should provide an answer such as Belle got a Crunch bar, Jasmine got a Snickers, and Cinderella got a Kit Kat bar.

Results

We begin with the results for the quantifier every, which was predicted to exhibit a subject-object asymmetry. Adults showed a strong preference for single answers over PLAs, even in situations where both answers are allowed. Adults produced PLAs only 4% of the time for subject-quantifier questions, and never produced them for object-quantifier questions. See Figure 3.

Children, by contrast, produced PLAs to subject-quantifier questions approximately half of the time and significantly more than adults (p < 0.01). The crucial test of their grammatical competence came with the object-quantifier questions, where PLAs are not allowed. Here, children produced PLAs 33% of the time, again significantly more than adults (p < 0.01). Thus children do overgeneralize PLAs in response to object-quantifier questions with every. Children do, however, produce fewer PLAs to object-quantifier questions than to subject-quantifier questions, a point we retun to below.

Figure 3. Production of pair-list answers for questions with every

We now turn to the results for the quantifier each. Recall that because each lands in a position high in the syntactic tree, and can take scope over the subject

Questions with every

Adults

Children wh-phrase at LF, PLAs are permitted with both subject-and object-quantifier questions. Interestingly, adultswho resisted PLAs with everyare drawn to them with each. See Figure 4. In addition, as predicted by [START_REF] Beghelli | The syntax of distributivity and pair-list readings[END_REF], adults produced significantly more PLAs to object-quantifier questions each, than to object-quantifier questions every (p < 0.01).

One might suspect, given the results with every and the distributivity properties of each, that children would increase their rate of PLAs with this quantifier. However, their rate of PLAs remains comparable with subjectquantifier questions and decreases with object-quantifier questions (although this difference was not significant p = 0.129, n.s.). In other words, compared to adults, who in fact did produce PLA in questions with both subject-and objectquantifier questions, children under-produced PLAs to question with each. Thus, children did not show a strong sensitivity to the choice of the quantifier.

Figure 4. Production of pair-list answers for questions with each

In order to detect any developmental trends in PLA production, we analyzed the two child age groups. While the data are preliminary, the trends are already quite clear. For questions with every, production of PLAs decreases with age. See Figure 5. For each the pattern is reversed: children exhibit a lower rate of PLAs than adults, and consistently so across child age groups. See Figure 6.

Discussion

We began this paper by observing that quantifiers and wh-expressions exhibit complex interactions in questions that give rise to structural ambiguities. These interactionsand specifically, the availability of PLAs with whichquestionsare constrained by the position of the quantifier and wh-word with respect to each other, and lexical factors such as the type of quantifier and the type of wh-word. With the quantifier every, PLAs are predicted to be possible only for subject-quantifier and not for object-quantifier questions, resulting in a

Questions with each

Subject quantifier Object quantifier subject-object asymmetry. With each, PLAs are predicted to be possible with both subject-and object-quantifier questions. Our results do not simply replicate previous studies. Nor do they simply reflect theoretical claims.

In line with previous results from [START_REF] Roeper | The Emergence of bound variable structures[END_REF], we showed that children do indeed overgeneralize PLAs relative to adults, producing them with every questions, regardless of quantifier position. The fact that they did so with our which object-quantifier questions (claimed to unequivocally bar PLAs) reinforces this observation. That the rate of PLAs in our studies is not as high as in previous acquisition studies may be a reflection of the use of who in those studies and which in ours. Adults did not display the anticipated subject-object asymmetry (allowing PLAs with subject-quantifier questions, but not allowed them with object-quantifier questions), because they seemed to strongly prefer single answers to every questions across the board.

The picture was different with each. Here, the strongly distributive quantifier was expected to give rise to PLAs more easily [START_REF] Beghelli | The syntax of distributivity and pair-list readings[END_REF], Szabolcsi 1997). This prediction was confirmed by the adults, whoin contrast to their performance with everystrongly preferred PLAs with each. Children were strikingly different. They not only produced fewer PLAs than adults, but displayed performance similar to questions with every. Thus, children do not seem to have drawn a sharp distinction between the two universal quantifiers.

This observation is not entirely surprising, given the results from recent child language studies, which show that children have a different interpretation of each than do adults. For example, [START_REF] Roeper | Quantifier spreading is not distributive[END_REF] found that when faced with a choice such as the one shown in Figure 7, and asked to judge two separate sentences (Every flower is in a vase and Each flower is in a vase), children chose picture C as the best match for the target sentence with every, and were evenly distributed across A, B, and C in their choice for the best match for the each sentence. By contrast, while adults sometimes found C acceptable for the each sentence, they never picked C as the best match. Roeper, Pearson & Grace argue that for children, exhaustivity of the quantifier is its defining property (and so children want all vases to be filled), and distributivity is not yet projected as a lexical feature. Syrett & Musolino (in press) also observed that children differed from adults in their interpretation of each. When asked to judge sentences such as Two girls each completed a puzzle in a scenario in which both girls had worked together to complete one puzzle (a 'collective' context), children accepted the sentence, indicating that each of the girls had in the puzzle event. Thus, they did not predicate the property 'complete a puzzle' of each girl, but rather allowed each girl to have participated in a 'puzzle completion' event.

Why would children exhibit non-adult-like behavior with each in these experiments and the current one reported here? One explanation might be that they are still learning what each means, and that they interpret it as a quantifier that bears properties of both every and each, allowing for both weakly and strongly distributive patterns. Possibly, in the child grammar, every can raise higher in the tree, just like each in the adult grammar. Children could therefore access a PLAs for questions with object every. That would explain why the production rates for PLAs are similar for every and each for children but different for adults. A question remains as to why children do not always produce PLAs to questions with each. It is possible that in child language each has properties similar to those of every, namely it does not always act as a strongly distributive quantifier, failing to take scope over the wh-term. In sum, our results favor a lexical rather than a structural explanation to the children's previously observed overgeneralization of PLA in questions with every. While our data do not reveal when the adult interpretation of every and each emerge, it should manifest itself when children have fully acquired the distributive properties of each quantifier and can therefore target the right landing site in the syntactic structure.

Figure 2 .

 2 Figure 2. Object-quantifier story

Figure 5 .Figure 6 .

 56 Figure 5. Production of pair-list answers by age group (every)

Figure 7 .

 7 Figure 7. Stimuli for every and each from Roeper, Pearson & Grace (2011)

Table 1 . Production of pair-list answers in Roeper & de Villiers (1991) Question Single answer Pair-list answer

 1

	Who did everyone pull t? (subject)	11%	73%
	Who pulled everyone?	(object)	26%	69%

Table 2 . Production of pair-list answers in Yamakoshi (2002) and revised count in parentheses

 2

	Question		Single answer	Pair-list answer
	What did everyone take?	(subject)	0%	62%
				(94%)
	Who took every vegetable? (object)	69%	8%
				(26%)

[START_REF] Roeper | The Emergence of bound variable structures[END_REF]'s pioneering studies investigated whether children produce PLAs to subject-quantifier questions, but refrain from doing so for object-quantifier questions. Children were shown pictures accompanied by


Bastien Cazaux
email: cazaux@lirmm.fr

Eric Rivals
email: rivals@lirmm.fr

Approximation of greedy algorithms for Max-ATSP, Maximal Compression, and Shortest Cyclic Cover of Strings

Given a directed graph G with weights on its arcs, the Maximum Asymmetric Travelling Salesman Problem (Max-ATSP) asks for a Hamiltonian path of maximum weight covering G. Max-ATSP, a central problem in computer science, is known to NP-hard and hard to approximate. In the general case, when the Triangle Inequality is not satisfied, the best approximation ratio known to date equals 2/3. Now consider the Overlap Graph for a set of finite words P := {s 1 , . . . , s p }: the directed graph in which an arc links two words with a weight equals to the length of their maximal overlap. When Max-ATSP is applied to the Overlap Graph, it solves the Maximal Compression or Shortest Superstring problem, where one searches for a string of minimal length having each input word as a substring. Again these problems are hard to approximate. Both for Max-ATSP and for Maximal Compression, good approximation algorithms use a cover of the graph by a set of cycles or of the words by a set of cyclic strings. These questions are known as Maximal Directed Cyclic Cover (MDCC) and as Shortest Cyclic Cover of Strings (SCCS), and can be solved in polynomial time. However, among these four problems, the approximation ratio achieved by a simple greedy algorithm is known only for Maximal Compression. In a seminal but complex proof, Tarhio and Ukkonen showed that it achieves 1/2 compression ratio. Taking advantage of the power of subset systems, we investigate the approximation of associated greedy algorithms for these four problems, and show they reach a ratio of 1/3 for Max-ATSP, 1/2 for Maximal Compression and for Maximal Cyclic Cover, and gives an exact solution for the Shortest Cyclic Cover of Strings. The proof for Maximal Compression is simpler than known ones. For these problems, greedy algorithms are easier to implement and often faster than existing approximation algorithms, an important fact since these problems have practical applications, for instance in data compression and computational biology.

Introduction

Given a set of words P = {s 1 , . . . , s p } over a finite alphabet, the Shortest Superstring (SS) or Maximal Compression (MC) problems ask for a shortest string u that contains each of the given words as a substring. It is a key problem in data compression and in bioinformatics, where it models the question of sequence assembly. Indeed, sequencing machines yield only short reads that need to be aggregated according to their overlaps to obtain the whole sequence of the target molecule [START_REF] Gusfield | Algorithms on Strings, Trees and Sequences[END_REF]. Two measures can be optimised for SS: either the length of the superstring is minimised, or the compression is maximised (i.e., S -|u| := ∑ s i ∈S |s i | -|u|). Unfortunately, even for a binary alphabet, SS is NP-hard [START_REF] Gallant | On finding minimal length superstrings[END_REF] and MAX-SNP-hard relative to both measures [START_REF] Blum | Linear approximation of shortest superstrings[END_REF]. Among many approximation algorithms, the best known fixed ratios are 2 11 23 for the superstring [START_REF] Mucha | Lyndon words and short superstrings[END_REF] and 2 3 for the compression [START_REF] Kaplan | Approximation algorithms for asymmetric tsp by decomposing directed regular multigraphs[END_REF]10]. A famous conjecture states that a simple, greedy agglomeration algorithm achieves a ratio 2 for the superstring measure, while it is known to approximate the maximum compression with ratio 1/2, but the later proofs are quite complex involving many cases of overlaps [START_REF] Tarhio | A greedy approximation algorithm for constructing shortest common superstrings[END_REF][START_REF] Turner | Approximation algorithms for the shortest common superstring problem[END_REF]. The best approximation algorithms use the Shortest Cyclic Cover of Strings (SCCS) as a procedure, which asks for a set of cyclic strings of total minimum length that collectively contain the input words as substrings. The SCCS problem can be solved in polynomial time in S [11,[START_REF] Blum | Linear approximation of shortest superstrings[END_REF].

These problems on strings can be viewed as problems on the Overlap Graph, where the input words are the nodes, and an arc represents the asymmetric maximum overlap between two words. Figure 2 on p.12 displays an example of overlap graph. Covering the Overlap Graph with either a maximum weight Hamiltonian path or a maximum weight cyclic cover gives a solution for the problems of Maximal Compression or of Shortest Cyclic Cover of Strings, respectively. This expresses the relation between the Maximum Asymmetric Travelling Salesman Problem (Max-ATSP) and Maximal Compression on one hand, as well as between Maximum Directed Cyclic Cover (Max-DCC) and Shortest Cyclic Cover of Strings on the other. Both Max-ATSP and Max-DCC have been extensively studied as essential computer science problems.

Hereditary systems were introduced recently to investigate the approximation performances of greedy algorithms in a unified framework [START_REF] Mestre | Greedy in Approximation Algorithms[END_REF]. With their help, we investigate the approximation achieved by greedy algorithms on these four problems and provide the results mentioned in the abstract. After introducing the required notation and concepts, we study the case of the Max-ATSP and Max-DCC problems in Section 2, then we focus on the Maximal Compression problem in Section 3, and state the results regarding Shortest Cyclic Cover of Strings in Section 3.2, before concluding.

Sets, strings, and overlaps.

We denote by #(Λ) the cardinality of any finite set Λ.

An alphabet Σ is a finite set of letters. A linear word or string over Σ is a finite sequence of elements of Σ. The set of all finite words over Σ is denoted by Σ ⋆ , and ε denotes the empty word. For a word x, |x| denotes the length of x. Given two words x and y, we denote by xy the concatenation of x and y. For every 1 ≤ i ≤ j ≤ |x|, x[i] denotes the i-th letter of x, and x[i ; j] denotes the substring x

[i]x[i + 1] . . . x[ j].
A cyclic string or necklace is a finite string in which the last symbol precedes the first one. It can be viewed as a linear string written on a torus with both ends joined.

Overlaps and agglomeration Let s,t, u be three strings of Σ ⋆ . We denote by ov(s,t) the maximum overlap from s over t; let r be prefix of s such that s = r . ov(s,t), then we denote the agglomeration of s over t by s ⊕ t := rt. Note that neither the overlap nor the agglomeration are symmetrical. Clearly, one has (s ⊕ t) ⊕ (t ⊕ u) = (s ⊕ t) ⊕ u.

Notation on graphs

We consider directed graphs with weighted arcs. A directed graph G is a pair (V G , E G ) comprising a set of nodes V G , and a set E G of directed edges called arcs. An arc is an ordered pair of nodes.

Let w be a mapping from E G onto the set of non negative integers (denoted N). The weighted directed graph G := (V G , E G , w) is a directed graph with the weights on its arcs given by w.

A route of G is an oriented path of G, that a subset of V G forming a chain between two nodes at its extremities. A cycle of G is a route of G where the same node is at both extremities. The weight of a route r equals the sum of the weights of its arcs. For simplicity, we extend the mapping w and let w(r) denote the weight of r.

We investigate the performances of greedy algorithms for different types of covers of a graph, either by a route or by a set of cycles. Let X be a subset of arcs of V G . X covers G if and only if each vertex v of G is the extremity of an arc of X.

Subset systems, extension, and greedy algorithms

A greedy algorithm builds a solution set by adding selected elements from a finite universe to maximise a given measure. In other words, the solution is iteratively extended. Subset systems, which are also called hereditary systems in French, are useful concepts to investigate how greedy algorithms can iteratively extend a current solution to a problem. A subset system is a pair (E, L) comprising a finite set of elements E, and L a family of subsets of E satisfying two conditions:

(HS1) L = / 0, (HS2) If A ′ ⊆ A and A ∈ L, then A ′ ∈ L. i.
Y ⊆ D \C with #(Y ) ≤ k satisfying D \Y ∪ {x} ∈ L.
The greedy algorithm associated with (E, L) and a weight function w is presented in Algorithm 1. Checking whether F ∪ {e i } ∈ L consists in verifying the system's conditions. In the sequel of this paper, we will simply use "the greedy algorithm" to mean the greedy algorithm associated to a subset system, if the system is clear from the context. A theorem from Mestre links k-extendibility and the approximation ratio of the associated greedy algorithm.

Theorem 1 (Mestre [START_REF] Mestre | Greedy in Approximation Algorithms[END_REF]). Let (E, L) be a k-extendible subset system. The associated greedy algorithm defined for the problem (E, L) with weights w gives a 1 k approximation factor.

Input : (E, L)
The elements e i of E sorted by increasing weight:

w(e 1 ) ≤ w(e 2 ) ≤ . . . ≤ w(e n ) F ← / 0 for i = 1 to n do if F ∪ {e i } ∈ L then F ← F ∪ {e i }; return F Algorithm 1:
The greedy algorithm associated with the subset system (E, L) and weight function w.

1.4 Definitions of problems and related work.

Graph covers

Let G := (V G , E G , w) be a weighted directed graph.
The well known Hamiltonian path problem on G requires that the cover is a single path, while the Cyclic Cover problem searches for a cover made of cycles. We consider the weighted versions of these two problems, where the solution must maximise the weight of the path or the sum of the weights of the cycles, respectively. In a general case, the graph is not symmetrical, and the weigh function does not satisfy the Triangle inequality. When a Hamiltonian path is searched for, the problem is known as the Maximum Asymmetric Travelling Salesman Problem or Max-ATSP for short. Max-ATSP is an important and well studied problem. It is known to be NP-hard and hard to approximate (precisely, Max-SNP hard). The best known approximation ratio of 2/3 is achieved by using a rounding technique on a Linear Programming relaxation of the problem [START_REF] Kaplan | Approximation algorithms for asymmetric tsp by decomposing directed regular multigraphs[END_REF]. However, the approximation ratio obtained by a simple greedy 20 th

′ = s i 1 ⊕ s i 2 ⊕ . . . ⊕ s i p , and then S -|s ′ | = ∑ p-1 j=1 |ov(s i j , s i j+1 )|.
Definition 1.4 (Shortest Superstring Problem (SS)). Input: Let p be a positive integer and P := {s 1 , s 2 , . . . , s p } be a set of p strings over Σ. Question: Find s ′ a superstring of P of minimal length.

Two approximation measures can be optimised:

• the length of the obtained superstring, that |s ′ |, or

• the compression of the input strings achieved by the superstring: S -|s ′ |.

The corresponding approximation problems are termed Shortest Superstring in the first case, or Maximal Compression in the second. These two problems have applications in data compression and in computational biology. Indeed, finding a superstring of a large set of short input sequences gives a solution to the DNA shotgun sequencing problem, which is encountered when one wishes to determine the complete nucleotidic sequence of a long gene, a chromosome, or a whole genome. The question of DNA assembly has attracted a lot of attention since the launch of Next Generation Sequencing technologies, which have revolutionised the process of DNA acquisition. These technologies have permitted an exponential increase in throughput, making acute the need for simple and efficient assembly algorithms.

Both the Maximal Compression and Shortest Superstring problems are NP-hard [START_REF] Gallant | On finding minimal length superstrings[END_REF] and Max-SNP hard [START_REF] Blum | Linear approximation of shortest superstrings[END_REF]. Numerous, complex algorithms have been designed for them, or their variants. Many are quite similar and use a procedure to find a Maximum Directed Cyclic Cover of the input strings . The best known approximation ratio for the Shortest Superstring was obtained in 2012 and equals 2 11 13 [START_REF] Mucha | Lyndon words and short superstrings[END_REF], although an optimal ratio of 2 has been conjectured in the 80's [START_REF] Tarhio | A greedy approximation algorithm for constructing shortest common superstrings[END_REF][START_REF] Blum | Linear approximation of shortest superstrings[END_REF].

For the Maximal Compression problem, two algorithms give a ratio of 2 Definition 1.5 (Shortest Cyclic Cover of Strings (SCCS)). Input: Let p ∈ N and P := {s 1 , s 2 , . . . , s p } be a set of p linear strings over Σ. Question: Find a set of cyclic strings of minimal cumulated length such that any input s i with 1 ≤ i ≤ p, is a substring of at least one cyclic string.

Several approximation algorithms for the Shortest Superstring problem uses a procedure to solve SCCS on the instance, which is based on a modification of a polynomial time algorithm for the assignment problem [11,[START_REF] Blum | Linear approximation of shortest superstrings[END_REF][START_REF] Gusfield | Algorithms on Strings, Trees and Sequences[END_REF]. This further indicates the importance of SCCS.

Both the Maximal Compression and the Shortest Cyclic Cover of Strings problems can be expressed as a cover of the Overlap Graph. In the Overlap Graph, the vertices represent the input strings, and an arc links s i to s j with weight s i ⊙ s j . Hence, the overlap graph is a complete graph with null or positive weights. An Hamiltonian path of this graph provides a permutation of the input strings; by agglomerating these strings in the order given by the permutation one obtains a superstring of P. Hence, the maximum weight Hamiltonian path induces a superstring that accumulates an optimal set of maximal overlaps, in other words a superstring that achieves maximal compression on P. Thus, a ρ approximation for Max-ATSP gives the same ratio for Maximal Compression. The same relation exists between the Shortest Cyclic Cover of Strings and Maximum Directed Cyclic Cover on graphs. Indeed, SCCS optimises P -∑ j |c j |, where c j is a cyclic string in the solution, and Max-DCC optimises the cumulated weight of the cycles of G. With the Overlap Graph, a minimal cyclic string is associated to each graph cycle by agglomerating the input strings in this cycle. Thus, the cumulated weight of a set of graph cycles corresponds to compression achieved by the set of induced cyclic strings. In other words, Shortest Cyclic Cover of Strings could also be called the Maximal Compression Cyclic Cover of Strings problem (and seen as a maximisation problem). Here again, the performance of a greedy algorithm for the Shortest Cyclic Cover of Strings problem remains open [START_REF] Weinard | On the greedy superstring conjecture[END_REF].

Maximum Asymmetric Travelling Salesman and Directed Cyclic Cover Problems

Let w be a mapping from E G onto the set of non negative integers and let G := (V G , E G , w) be a directed graph with the weights on its arcs given by w. We first define a subset system for Max-ATSP and its accompanying greedy algorithm.

Definition 2.1. We define the pair (E G , L S ) where E G is the arc set of G and L S the set of subsets, F, of E G satisfying:

(L1) ∀x, y and z ∈ V G , (x, z) and (y, z) ∈ F implies x = y, (L2) ∀x, y and z ∈ V G , (z, x) and (z, y) ∈ F implies x = y, (L3) for any r ∈ N ⋆ , there does not exist any cycle ((x 1 , x 2 ), . . . , (x r-1 , x r ), (x r , x 1 )) in F, where ∀k ∈ {1, . . . , r}, x k ∈ V G .

Remark: .

• In other words, for a subset F of E G , Condition (L1) (resp. (L2)) allows only one ingoing (resp. outgoing) arc for each vertex of G.

• For all F ∈ L S and for any v ∈ V G , the arc (v, v) cannot belong to F, by Condition (L3) for r = 1.

• If in condition (L 3 ), one changes the set of forbidden values for r, the subset system addresses a different problem. As the proofs in this section do not depend of r, all results remain valid for these problems as well. For instance, with r ∈ {1}, only cycles of length one are forbidden; the solution is either a maximal path or cyclic cover with cycles of length larger than one. The 1/3 approximation ratio obtained in Theorem 4 remains valid.

We will consider later the case where all cycles are allowed (i.e., r ∈ / 0). (L1) ∀s i , s j and s k ∈ S, s i ⊙ s k and s j ⊙ s k ∈ F ⇒ i = j, i.e. for each string, there is only one overlap to the left (L2) ∀s i , s j and s k ∈ S, s k ⊙ s i and s k ⊙ s i ∈ F ⇒ i = j, and only one overlap to the right (L3) for any r ∈ N ⋆ , there exists no cycle (s i 1 ⊙ s i 2 , . . . , s i r-1 ⊙ s i r , s i r ⊙ s i 1 ) in F, such that ∀k ∈ {1, . . . , r}, s i k ∈ S.

Proposition 2. (E G , L S ) is a subset system.
For each set F := {s i 1 ⊙ s i 2 , . . . , s i p-1 ⊙ s i p } that is a maximal element of L P for inclusion, we denote by l(F) the superstring of S obtained by agglomerating the input strings of P according to the order induced by F:

l(F) := s i 1 ⊕ s i 2 ⊕ . . . ⊕ s i p .
First, knowing that Maximal Compression is equivalent to Max-ATSP on the Overlap Graph (see Section 1.4.2), we get a 1 3 approximation ratio for Maximal Compression as a corollary of Theorem 4. Another way to obtain this ratio is to show that the subset system is 3-extendible (the proof is identical to that of Proposition 3) and then use Theorem 1. However, the following example shows that the system (E P , L P ) is not 2-extendible.

Example 1. The subset system (E P , L P ) is not 2-extendible. Let P := {s 1 , s 2 , s 3 , s 4 , s 5 }, C := / 0, x := s 1 ⊙ s 2 . Then clearly C ∪ {x} belongs to L P and the set D := {s 1 ⊙ s 3 , s 4 ⊙ s 2 , s 5 ⊙ s 1 , s 2 ⊙ s 5 } is an extension of C. However, when searching for a set Y such that Y included in D \C = D and such that (D \Y ) ∪ {x} ∈ L P then s 1 ⊙ s 3 , s 4 ⊙ s 2 must be removed to avoid violating (L1) or (L2), and at least one among s 5 ⊙ s 1 , s 2 ⊙ s 5 must be removed to avoid violating (L3). It follows that #(Y ) ≥ 3.

To prove a better approximation ratio for the greedy algorithm, we will need the Monge inequality [START_REF] Monge | Mémoire sur la théorie des déblais et des remblais[END_REF] adapted to word overlaps. Lemma 6. Let be F ∈ L P and x ∈ E P , w(OPT (F ∪ {x})) ≤ w(OPT (F)).

Now we can prove a better approximation ratio.

Theorem 7. The approximation ratio of the greedy algorithm for the Maximal Compression problem is 1 2 . Proof. To prove this ratio, we revisit the proof of Theorem 1 in [START_REF] Mestre | Greedy in Approximation Algorithms[END_REF].

Let x 1 , x 2 , . . . , x l denote the elements in the order in which the greedy algorithm includes them in its solution F, and let F 0 := / 0, . . . , F l denote the successive values of the set F during the algorithm, in other words F i := F i-1 ∪ {x i } (see Algorithm 1 on p. 3). The structure of the proof is first to show for any element x i incorporated by the greedy algorithm, the inequality w(OPT (F i-1 )) ≤ w(OPT (F i )) + w(x i ), and second, to reason by induction on the sets F i starting with F 0 .

One knows that OPT (F i-1 ) is an extension of F i-1 . By the greedy algorithm and by the definitions of F i-1 and x i , one gets F i-1 ∪ {x i } ∈ L P . As x i ∈ E P , there exist s p and s o such that x i = s p ⊙ s o . Like in the proof of Proposition 3, let Y i denote the subset of elements of OPT (F i-1 ) \ F i-1 of the form s p ⊙ s k , s k ⊙ s o , or s k ⊙ s p , where s k ⊙ s p belongs to a cycle in OPT (F i-1 ) ∪ {x i }. Thus, OPT (F i-1 ) \Y i ∪ {x i } ∈ L P , and Indeed, w(OPT

w(OPT (F i-1 )) = w(OPT (F i-1 ) \Y i ∪ {x i }) + w(Y i ) -w(x i ), ≤ w(OPT (F i )) + w(Y i ) -w(x i ).
(F i-1 ) \ Y i ∪ {x i }) ≤ w(OPT (F i )) because OPT (F i-1 ) \ Y i ∪ {x i } is an extension of F i-1 ∪ {x i } and because OPT (F i
) is an extension of maximum weight of F i-1 ∪ {x i }. Now let us show by contraposition that for any element y ∈ Y i , w(y) ≤ w(x i ). Assume that there exists y ∈ Y i such that w(y) > w(x i ). As y / ∈ F i-1 , y has already been considered by the greedy algorithm and not incorporated in the F. Hence, there exists j ≤ i such that F j ∪ {y} / ∈ L P , but F j ∪ {y} ⊆ OPT (F i-1 ) ∈ L P , which is a contradiction. Thus, we obtain w(y) ≤ w(x i ) for any y ∈ Y i . Now we know that #(Y i ) ≤ 3. Let us inspect two subcases.

Case

1 : #(Y i ) ≤ 2.
We have w(Y ) ≥ 2w(x i ), hence w(OPT (F i-1 )) ≤ w(OPT (F i )) + w(x i ).

Case ). This situation is illustrated in Figure 1.

We have w(OPT

(F i-1 ) \Y i ∪ {x i , s k ⊙ s k ′ }) ≤ w(OPT (F i-1 ∪ {x i , s k ⊙ s k ′ })), because OPT (F i-1 ) \Y i ∪ {x i , s k ⊙ s k ′ } is an extension of F i-1 ∪ {x i , s k ⊙ s k ′ } and OPT (F i-1 ∪ {x i , s k ⊙ s k ′ }) is a maximum weight extension of F i-1 ∪ {x i , s k ⊙ s k ′ }. As w(OPT (F i-1 ∪ {x i , s k ⊙ s k ′ })) ≤ w(OPT (F i-1 ∪ {x i }))
, by Lemma 6 one gets:

w(OPT (F i-1 )) = w(OPT (F i-1 ) \Y i ∪ {x i , s k ⊙ s k ′ }) + w(Y i ) -w(x i ) -w(s k ⊙ s k ′ ), ≤ w(OPT (F i-1 ∪ {x i , s k ⊙ s k ′ })) + w(Y i ) -w(x i ) -w(s k ⊙ s k ′ ), ≤ w(OPT (F i )) + w(Y i ) -w(x i ) -w(s k ⊙ s k ′ ). As Y i = {s p ⊙ s k ′ , s k ⊙ s o , s k ′′ ⊙ s p }, one obtains w(OPT (F i-1 )) ≤ w(OPT (F i )) -w(s k ⊙ s k ′ ) + w(Y i ) -w(x i ), ≤ w(OPT (F i )) -w(s k ⊙ s k ′ ) + w(s p ⊙ s ′ k ) + w(s k ⊙ s o ) + w(s k ′′ ⊙ s p ) -w(x i ). ≤ w(OPT (F i )) + w(s k ′′ ⊙ s p ) ≤ w(OPT (F i )) + w(x i ).
Remembering that OPT ( / 0) is an optimum solution, by induction one gets

w(OPT (F 0 )) ≤ w(OPT (F l )) + l ∑ i=1 w(x i ) ≤ w(F l ) + w(F l ) ≤ 2w(F l ).
We can substitute w(OPT (F l )) by w(F l ) since F l has a maximal weight by definition. Let s opt be an optimal solution for Maximal Compression, P -|s opt | = w(OPT ( / 0)). As F l is maximum, l(F l ) is the superstring of P output by the greedy algorithm and thus, P -|l(F l )| = w(F l ). Therefore, Finally, we obtain the desired ratio: the greedy algorithm of the subset system achieves an approximation ratio of ). Since we are adding x i to OPT (F i-1 ), we need to remove three elements in red:

s k ′′ ⊙ s p , s p ⊙ s k ′ , s k ⊙ s o .

Equivalence between the greedy algorithm and algorithm greedy

Here, we prove that the algorithm greedy defined by Tarhio and Ukkonen [START_REF] Tarhio | A greedy approximation algorithm for constructing shortest common superstrings[END_REF] and studied by Blum and colleagues [START_REF] Blum | Linear approximation of shortest superstrings[END_REF] for the Maximal Compression problem, computes exactly the same superstring as the greedy algorithm of the subset system (E P , L P ) (see Definition 3.1 on p. 6). This is to show that these two algorithms are equivalent in terms of output and that the approximation ratio of 1/2 of Theorem 7 is valid for both of them. Remind that the input, P := {s 1 , s 2 , . . . , s p }, is a set of p strings of Σ ⋆ .

Proposition 8. Let F be an maximal element for inclusion of L P . Thus, there exists a permutation of the input strings, that is a set {i 1 , . . . , i p } = {1, . . . , p} such that F = {s i 1 ⊙ s i 2 , s i 2 ⊙ s i 3 , . . . , s i p-1 ⊙ s i p }.

Proof. By the condition (L3), cycles are forbidden in F. Hence there exist s d 1 , s x ∈ S such that s d 1 ⊙ s x ∈ F, and for all s y ∈ S, s y ⊙ s d 1 / ∈ F. Thus, let (i j ) j∈I be the sequence of elements of P such that i 1 = d 1 , for all j ∈ I such that j + 1 ∈ I, s i j ⊙ s i j+1 ∈ F, and the size of I is maximum. As F has no cycle (condition L3), I is finite; then let us denote by t 1 its largest element. We have for all s y ∈ P, s t 1 ⊙ s y / ∈ F. Hence, ∪ j∈I i j is the interval comprised between s d 1 and s t 1 . Assume that F \ {∪ j∈I i j } = / 0. We iterate the reasoning by taking the interval between s d 2 and s t 2 and so on until F is exhausted. We obtain that F is the set of intervals between s d i and s t i . By the condition (L1) and (L2), s t 1 (resp. s d 2 ) is in the interval between s d j and s t j ⇒ j = 1 (resp. j = 2). As s t 1 ⊙ s d 2 ∈ E, and F ∪ {s t 1 ⊙ s d 2 } ∈ L P , F is not maximum, which contradicts our hypothesis.

We obtain that F \ {∪ j∈I i j } = / 0, hence the result.

For each set F := {s i 1 ⊙ s i 2 , . . . , s i p-1 ⊙ s i p } that is a maximal element of L P for inclusion, remind that l(F) denotes the superstring of S obtained by agglomerating the input strings of P according to the order induced by F: l(F) := s i 1 ⊕ s i 2 ⊕ . . . ⊕ s i p .

The algorithm greedy takes from set P two words u and v having the largest maximum overlap, replaces u and v with a ⊕ b in P, and iterates until P is a singleton. Proposition 9. Let F be the output of the greedy algorithm of subset system (E P , L P ), and S the output of Algorithm Greedy for the input P. Then S = {l(F)}.

  Example: Let be three words abbaa, baabb and aabba. ov(abbaa, baabb) = baa and abbaa ⊕ baabb = abbaabb. Considering possible agglomerations of these words, we get w 1 = abbaa ⊕ baabb ⊕ aabba = abbaabb ⊕ aabba = abbaabba, w 2 = aabba ⊕ abbaa ⊕ baabb = aabbaa ⊕ baabb = aabbaabb and w 3 = baabb ⊕ abbaa ⊕ aabba = baabbaa ⊕ aabba = baabbaabba. Thus, |w 1 | = |pr(abbaa, baabb)| + |pr(baabb, aabba)| + |aabba| = |ab| + |b| + |aabba| = 2 + 1 + 5 = 8, S -|w 1 | = 15 -8 = 7 and |ov(abbaa, baabb)| + |ov(baabb, aabba)| = |baa| + |aabb| = 3 + 4 = 7

  20 th Oct. 2013 2 LIRMM R.R. 2013

Definition 1 . 1 (

 11 Max-ATSP). Max-ATSP is the problem where one searches for a maximum weight Hamiltonian path on G.

  20 th Oct. 2013 5 LIRMM R.R. 2013

Lemma 5 .

 5 Let s 1 , s 2 , s 3 and s 4 be four different words satisfying |ov(s 1 , s 2 )| ≥ |ov(s 1 , s 4 )| and |ov(s 1 , s 2 )| ≥ |ov(s 3 , s 2 )|. So we have : |ov(s 1 , s 2 )| + |ov(s 3 , s 4 )| ≥ |ov(s 1 , s 4 )| + |ov(s 3 , s 2 )|. When for three sets A, B,C, we write A ∪ B \ C, it means (A ∪ B) \ C. Let A ∈ L P and let OPT (A) denote an extension of A of maximum weight. Thus, OPT ( / 0) is an element of L P of maximum weight. Next lemma follows from this definition.

  20 th Oct. 2013 7 LIRMM R.R. 2013

1 2 (

 12 P -|s opt |) ≤ P -|l(F l )| .

  20 th Oct. 2013 9 LIRMM R.R. 2013

  e., L is close by taking a subset.Let A, B ∈ L P . One says that B is an extension of A if A ⊆ B and B ∈ L P . A subset system (E, L) is said to be k-extendible if for all C ∈ L and x / ∈ C such that C ∪ {x} ∈ L, and for any extension D of C, there exists a subset

  Oct. 2013 3 LIRMM R.R. 2013 algorithm remains an interesting open question, especially, since other approximation algorithms are usually less efficient than a greedy one. As later explained, Max-ATSP is strongly related to the Shortest Superstring and the Maximal Compression problems on strings.If a set of cycles is needed as a cover the graph, the problem is called Maximum Directed Cyclic Cover. In the general setup, cycles made of singletons are allowed in a solution.Definition 1.2 (Max Directed Cyclic Cover). Maximum Directed Cyclic Cover is the problem where one searches for a set of cycles of maximum weight that collectively cover G.To our knowledge, the performance of a greedy algorithm for Maximum Directed Cyclic Cover (Max-DCC) has not yet been established, although variants of Max-DCC with binary weights or with cycles of predefined lengths have been studied[START_REF] Bläser | Approximating maximum weight cycle covers in directed graphs with weights zero and one[END_REF][START_REF] Bläser | Improved approximation algorithms for metric maximum atsp and maximum 3-cycle cover problems[END_REF].1.4.2 Superstring and Maximal CompressionDefinition 1.3 (Superstring). Let P = {s 1 , s 2 , . . . , s p } be a set of p strings of Σ ⋆ . A superstring of P is a string s ′ such that s i is a substring of s ′ for any i in[1, p].Let us denote the sum of the lengths of the input strings by S := ∑ s i ∈S |s i |. For any superstring s ′ , there exists a set {i 1 , . . . , i p } = {1, . . . , n} such that s

  2 : #(Y i ) = 3.There exists s k and s k ′ such that s p ⊙ s k ′ and s k ⊙ s o are in Y i . By Lemma 5, we have w(x i ) + w(s k ⊙ s k ′ ) ≥ w(s p ⊙ s k ′ ) + w(s k ⊙ s o ). As s p ⊙ s k ′ and s k ⊙ s o belong to OPT (F i-1 ), one deduces s k ⊙ s k ′ / ∈ OPT (F i-1 ). get OPT (F i-1 ) \ Y i ∪ {x i , s k ⊙ s k ′ } ∈ L P . Indeed, as Y i ⊆ OPT (F i-1 ),neither a right overlap of s k , nor a left overlap of s k ′ can belong to OPT (F i-1 ). Furthermore, adding s k ⊙ s k ′ to OPT (F i-1 ) \ Y i ∪ {x i } cannot create a cycle, since otherwise a cycle would have already existed in OPT (F i-1

	We

  Figure 1: Impossibility to create a cycle by adding s k ⊙ s k ′ to OPT (F i-1 ) \Y i ∪ {x i }, without having an already existing cycle in OPT (F i-1

	s k ′′		s i 1
	s p	x i	s 0
	s k ′		s k
			1
			2
	for the Maximal Compression problem.
	20 th Oct. 2013	8	LIRMM R.R. 2013

[START_REF] Kaplan | Approximation algorithms for asymmetric tsp by decomposing directed regular multigraphs[END_REF] 10]. A seminal work gave a proof of an approximation ratio of 1/2 by an algorithm that iteratively updates the input set by agglomerating two maximally overlapping strings until one string is left[START_REF] Tarhio | A greedy approximation algorithm for constructing shortest common superstrings[END_REF]. This algorithm was termed greedy but does not correspond to a greedy algorithm for it modifies the original input set. We demonstrate in Appendix that this algorithm yields the same result than a greedy algorithm defined for an appropriate subset system. Another proof of this ratio was given in[START_REF] Turner | Approximation algorithms for the shortest common superstring problem[END_REF]. Both proofs are quite intricate and include many subcases[START_REF] Tarhio | A greedy approximation algorithm for constructing shortest common superstrings[END_REF]. Thanks to subset systems, we provide a much simpler proof of this approximation ratio for Maximal Compression by a greedy algorithm, as well as an optimal and polynomial greedy algorithm for the problem of Max Cyclic Covers on Strings. 20 th Oct. 2013

LIRMM R.R. 2013

Proof. For (HS1), it suffices to note that / 0 ∈ L S .For (HS2), we must show that each subset of an element of L S is an element of L S . This is true since Conditions (L1), (L2), and (L3) are inherited by any subset of an element of L S .

Next proposition shows that the defined subset system is 3-extendible.

Maximal Compression and Shortest Cyclic Cover of Strings

Blum and colleagues [START_REF] Blum | Linear approximation of shortest superstrings[END_REF] have designed an algorithm called greedy that iteratively constructs a superstring for both the Shortest Superstring and Maximal Compression problems. As mentioned in introduction, this algorithm is not a greedy algorithm per se. Below, we define a subset system corresponding to that of Max ATSP for the Overlap Graph, and study the approximation of the associated greedy algorithm. Before being able to conclude on the approximation ratio of the greedy algorithm of [START_REF] Blum | Linear approximation of shortest superstrings[END_REF], we need to prove that greedy computes exactly the same superstring as the greedy algorithm of the subset system of Definition 3.1. This proof is given in Appendix. Knowing that these two algorithms are equivalent in terms of output, the approximation ratio of Theorem 7 is valid for both of them. From now on, let P := {s 1 , s 2 , . . . , s p } be a set of p strings of Σ ⋆ . The subset system for Maximal Compression is similar to that of Max-ATSP. For any two strings s,t, s ⊙ t represents the maximum overlap of s over t 1 . We set E P = {s i ⊙ s j | s i and s j ∈ P}. Hence, E P is the set of maximum overlaps between any two words of S. Definition 3.1 (Subset system for Maximal Compression). Let L P as the set of F ⊆ E P such that:

1 s ⊙ t differs ov(s,t), which is a word. s ⊙ t is the fact that s can be aggregated with t according to their maximal overlap. 20 th Oct. 2013 6 LIRMM R.R. 2013

Proof. First, see that for any i between 1 and p, there exists s j and s k such that e i = s j ⊙ s k . If F ∪ {e i } ∈ L P , then by Conditions (L1) and (L2), one forbids any other left overlap of s k or any other right overlap of s j are prohibited in the following. As cycles are forbidden by condition (L3), one will finally obtain the same superstring by exchanging the pair s j and s k with s j ⊕ s k in E.

The algorithm greedy from [START_REF] Tarhio | A greedy approximation algorithm for constructing shortest common superstrings[END_REF] can be seen as the greedy algorithm of the subset system (E P , L P ). By the definition of the weight w, the later also answers to the Maximal Compression problem. Both algorithms are thus equivalent.

Shortest Cyclic Cover of Strings

A solution for MC must avoid overlaps forming cycles in the constructed superstring. However, for the Shortest Cyclic Cover of Strings problem, cycles of any positive length are allowed. As in Definition 3.1, we can define a subset system for SCCS as the pair (E P , L C ), where L C is now the set of F ⊆ E P satisfying only condition (L1) and (L2). A solution for this system with the weights defined as the length of maximal overlaps is a set of cyclic strings containing the input words of P as substrings. One can see that the proof of Theorem 7 giving the 1/2 ratio for MC can be simplified to show that the greedy algorithm associated with the subset system (E P , L C ) achieves a 1/1 approximation ratio, in other words exactly solves SCCS.

Theorem 10. The greedy algorithm of (E P , L C ) exactly solves Shortest Cyclic Cover of Strings problem in polynomial time.

Conclusion

In this work, we investigated the approximation performance of greedy algorithms on well known problems using the power of subset systems. Greedy algorithms are algorithmically simpler, and usually easier to implement than more complex approximation algorithms. For instance, the upper and lower bounds of approximation are still being refined for the Shortest Superstring and Maximal Compression problems. It is important to know how good greedy algorithms are. Here, we gave a new and simpler proof of the 1/2 approximation ratio for Maximal Compression, and have shown that the greedy algorithm solves the Shortest Cyclic Cover of Strings problem exactly.

For the cover of graphs with maximum weight Hamiltonian path or set of cycles, the subset system and its associated greedy algorithm, provides an approximation ratio for a variety of problems, since distinct kinds of cycles can be forbidden in the third condition of the subset system (see Def.


Eduardo Mucelli

Rezende Oliveira

Aline Carneiro Viana

Des Routines Quotidiennes aux Meilleurs Services Réseaux

Keywords: routine, réseaux, services réseaux routine, networks, network services

Dans ce travail, nous évaluons le comportement routinière des personnes et soulignons les moyens de l'explorer an de fournir de meilleurs services réseaux. Nous avons étudié deux ensembles de données réelles décrivant plus de 6 ans de trajectoires des personnes dans leur vie quotidienne. Les résultats montrent que les personnes tendent en eet à prendre des chemins les plus courts quelle que soit le mode de transport. En outre, il s'agit d'un comportement collectif, pas un comportement spécique d'un certain groupe de personnes. Enn, les personnes manifestent deux autres caractéristiques sur leurs habitudes de mobilité: trajectoires très connées et répétitives.

Nous avons alors présenté plusieurs scénarios dans lesquels des solutions de réseaux peuvent être fournies en protant de ces comportements.

Introduction

People are routinary semi-rational entities, they have regular circles of actions guided by their decisions but unexpected situations may interfere on their directions [START_REF] Hamermesh | Routine[END_REF]. A person may change their itinerary due to a trac jam, problems on the public transportation, etc. When choosing an itinerary, people tend to use the shortest-path to reach their destination, also known as "desire line". The desire line is the shortest path between origin and destination, and expresses the way a person would like to go, if such a way were available [START_REF] Throgmorton | Desire lines : The chicago area transportation study and the paradox of self in post-war america[END_REF]. Furthermore, the people's itinerary is characterized by its connement, i.e., despite of choosing the shortest-paths, people will roam repetitively close by their main physical address [3].

Social ties among users have been widely exploited in opportunistic mobile networks to favor network services [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF][START_REF] Pietilänen | Dissemination in opportunistic social networks : the role of temporal communities[END_REF]. Nevertheless, still few works have been investigating user mobility in terms of their trajectories and daily space-time routines. On the other hand, we are going to assess the trajectories that people produce on their daily activities in two cities counting more than 2200 days span in order to understand how short and routinary the routes are.

To accomplish our objective, we study real-life mobility traces (cf. Section 3) of people in two metropolitan areas, namely Beijing and Tokyo, and measure two key characteristics of their routines, Connement (cf. Section 3.3) and Shortest-paths (cf. Section 3.4). Results reveal that 83% and 95% of the trajectories for Beijing and Tokyo, respectively have, at most, 10 km maximum displacement, i.e., people have their mobility conned. Furthermore, results show that, on average, 70% of the trajectories are, at most, half longer than the shortest path regardless of the transportation mode. Section 4 discusses some scenarios in which network solutions might take advantage of daily trajectories based on the measurements herein presented in order to provide people with better network services. Finally, Section 5 concludes this work.

Related Work

Human mobility has been widely studied, mainly focusing on the relation between people.

Remarkably, [START_REF] Milgram | The small world problem[END_REF] studied the implication of mobility on how separated people are and concluded that, in United States, people seemed to be separated by three acquaintance links.

More recently, the shortness of displacement was assessed by analysing the circulation of bank notes in the United States [3]. From a total of 20,540 short-time trajectories originating across the United States, results for three major cities, namely Seattle, New York, Jacksonville, shown that the probability of a trajectory measuring less than 10 km were 57.7%, 57.7% and 71.4%, respectively. On contrary to bank notes, our data is represented by GPS tracks which seems to be one of the most accurate ways to track mobility of people.

Regarding routinary visit of places, [START_REF] Papandrea | How many places do you visit a day[END_REF] proposed a solution to identify points of interest based on people's mobility characteristics. Our work diers since we are not interested on the points of interest but on the routinary characteristics present on people's trajectories.

Evaluation

To assess the routinary characteristics on people's daily lives we have used two datasets describing mobility on two big metropolitan areas, Beijing and Tokyo. The following subsections describe their characteristics.

Datasets

In this work, we are using two datasets, GeoLife on its latest version [START_REF] Zheng | Geolife : A collaborative social networking service among user, location and trajectory[END_REF] and a crawled dataset from OpenStreetMap [START_REF] Haklay | Openstreetmap : User-generated street maps[END_REF]. GeoLife is considered to be unique in the literature. This is due to the fact that it provides a rich view of people mobility using 11 dierent transportation modes in an urban area for a long period of time. It provides geolocalized and timestamped points from 182 people during spread on 1600 days, from April 2007 to October 2011, mostly in Beijing.

OpenStreetMap is collaborative open geodata online map that started in 2008 and currently has more than 1.3 million registered users. On OpenStreetMap, an user may upload his GPS tracks using GPX format that describes his geolocalized coordinates during the time. From it we have crawled user GPS tracking data from several cities using their API 1 . From this set we have chosen to use a subset containing information from users in Tokyo, one of the biggest cities in terms of available data. Tokyo dataset contains 88 people during 606 days from August 2007 to September 2013.

For each person, both datasets provide a set of geolocalized points, i.e., a GPS trajectory ascendingly sorted by timestamp. Trajectory represents how people moves around and is described as a set of points representing GPS coordinates periodically collected. In GeoLife dataset, people may move around building their trajectories using at most ten dierent transportation modes such as taxi, bike, run, bus, walk, train, subway, car, boat, and motorcycle. It is important to enhance that transportation mode information is not available for all trajectories on GeoLife and it is not available at all in Tokyo dataset. When it comes to assess mobility of people, the transportation mode is an important information. Indeed, transportation mode could change completely the network demands coming from people's devices : e.g., a person riding a bike has a dierent context than someone inside a bus, therefore, the former will be less susceptible to use the phone than the latter. In order to label the unlabeled trajectories, we have created a simple model that sets a transportation mode depending on the average speed in which the person is traveling. Section 3.2 describes in details how trajectory labeling was performed.

Moreover, to better understand specic behaviors inherent from dierent periods of the day, every day is divided into four periods of 6 hours, from 00 :00 to 05 :59, from 06 :00 to 11 :59, from 12 :00 to 17 :59, and from 18 :00 to 23 :59.

Labeling

Not every trajectory from the datasets herein considered are labeled with transportation modes. That is due to the fact that labeling was not mandatory for people participating on the GeoLife experiment nor it is an expected information on OpenStreetMap GPS data. A trajectory may have at least one transportation mode label. Each subset of points with a unique transportation mode contained in a trajectory is called leg. For example, a trajectory composed by two legs, "car" and "walk" representing a situation in which a person went by car to his work, parked the car and went walking until his oce.

Our model labels trajectories by their average speed, which is calculated considering both the length and the duration of the traveled leg. The result is matched against known speed ranges on the city. Table 1 describes average speed ranges by transportation mode in Beijing. We have used the same ranges to assign labels to the legs in Tokyo. Lets consider we have an unlabeled leg l traveled with average speed of 5 m/s. The transportation mode of a leg will be used to calculate its known shortest path. Therefore, in cases where labels are dividing a speed range, i.e., (1) 'bike' and 'run' and (2) 'taxi', 'motorcycle' and 'car', there is not negative impact on assigning a specic label instead of another in the same range. That is because the shortest path for labels in (1) is calculated dierently for labels in (2) (cf. Section 3.4).

Connement

To understand how the routine occurs on our scenario, we have measured how conned and repetitive the trajectories are.

In order to measure how conned are the trajectories, for each trajectory, we have calculated the maximum displacement, i.e., the distance between its initial and farthest point (not necessarily the last point). Fig. 1 presents the CCDF of the maximum displacement for all trajectories grouped by period on both datasets. It shows that 83% and 95% of the trajectories for Beijing and Tokyo respectively, have at most, 10 km maximum displacement and the period of the day does not aect this behavior. This result shows that generally people do not move far away from their starting point, and presents high connement. Results shown in [3] reveal that the percentage of trajectories with displacement less than 10km ranged from 52% to 71%. GPS tracking seems to be one of the most accurate ways to track mobility of people. Therefore, we believe that the higher connement presented in our results is a more precise measurement of human displacement on an urban scenario.

People with conned mobility tend to repetitively visit the same areas. To understand how people explore the regions, central Beijing and Tokyo were divided into square-shapped cells of 50 m 2 summing up 800 and 916 thousand cells, respectivelly. Then, we have calculated the number of unique cells (N U C) and total cells (N T C) that each trajectory visited. To quantitatively express the percentage of connement of a trajectory, a metric called Repetitiveness was conceived and is represented as the following :

N T C-N U C N T C * 100
Repetitiveness of a trajectory represents how repetitive is the route described by this trajectory. Regardless of the period of the day, trajectories present a considerable amount of repetitivity on both datasets. In Beijing, 90%, 89%, 90% and 92% of the performed trajectories present at most 50% of repetitiveness (i.e., half of the cells are repetitively visited) for periods from 00 :00 to 05 :59, from 06 :00 to 11 :59, from 12 :00 to 17 :59, and from 18 :00 to 23 :59, respectively.

Tokyo presents similar results, 98% 93% 94% 95% for periods from 00 :00 to 05 :59, from 06 :00 to 11 :59, from 12 :00 to 17 :59, and from 18 :00 to 23 :59, respectively. An interesting aspect of this results is to understand if the repetitiveness is related to the amount of trajectories per-formed by people and possibly to the amount of visited cells : "Does repetitiveness occurs less where less trajectories are performed ?". Revisiting areas is a consistent personal behavior that does not rely on the amount of trajectories that were performed on a certain period. In Beijing, both periods from 06 :00 to 11 :59 and from 00 :00 to 05 :59 have high and similar repetitiveness rates but the former has 6.4 times more trajectories than the latter. Similarly in Tokyo, period from 12 :00 to 17 :59 has 21 times more trajectories than the period from 00 :00 to 05 :59 but they present similar results.

On the other hand, repetitiveness also may be used to represent how repetitively a cell receives visits. The repetitiveness of a cell is based on the number of unique users (N U U ) and total users (N T U ) that visited it as following : values due to people going to and from their daily activities commuting in those station.

N T U -N U U N T U *

Shortest-paths

The concept of "desire lines" states that people tend to choose the shortest-paths to arrive on their destinations. In order to verify that, we have compared the length of each traveled leg against the length of the corresponding shortest path considering the same initial and nal points of the original leg. Dividing the length of the original leg by the length of the shortest path allows us measuring how longer the path made by a person is from the shortest path. We have used Google Directions API 2 to compute the shortest path. The API receives the coordinates of both initial and nal points and a travel mode, i.e., transportation mode. Then, it returns the shortest path considering the restrictions imposed by the existing routes and obstacles in the city for a specic transportation mode. Note that, we only have considered transportation modes where people have decision control of their paths. This excludes for example, buses, boats or trains.

Legs traveled by walking, running, and biking had their lengths divided by their respective shortest paths computed while using the API in walking mode. Google Directions API indeed has a bicycling travel mode, but at the moment, it does not contain routes neither in Beijing nor 2. https://developers.google.com/maps/documentation/directions Inria q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q qq q q q qq q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q qq q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 10 -4 (a) Beijing q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 10 -3 in Tokyo. Legs traveled by taxi, car, and motorcycle had their lengths divided by results of the API in the driving mode. Fig. 3 shows the CCDF of the ratio between the original legs length and the Google shortest path, by transportation mode and period of the day.

For Beijing, it shows that the periods from 00 :00 to 05 :59, from 06 :00 to 11 :59, from 12 :00 to 17 :59, and from 18 :00 to 23 :59 present, respectively, 60%, 72%, 65% and 79% of the legs measuring, at most, half longer than the shortest path. That results show that on late night people tend to walk around not directly going to their destination. Indeed, on late night people tend to go for bars, night clubs and are more susceptible to create routes that are way longer than the shortest ones. On the other hand, periods representing early morning and early night show high percentage of legs closest to the shortest one and describing how people go directly to their destinations, e.g., work, home, etc. The period containing the early afternoon hours present an intermediate percentage of legs close to the shortest path. Indeed, this period mixes people walking around careless about shortest paths (e.g, someone shopping, or looking for restaurants), and people more concerned about their being on time (e.g, people coming back from the lunchtime towards the work). Moreover, it is possible to see that the length ratio does not change in function of the transportation mode. It shows that regardless of the transportation mode, people tend to be oriented by the shortest paths.

On the other hand, Tokyo presents 56%, 49%, 46% and 61% ratio for periods from 00 :00 to 05 :59, from 06 :00 to 11 :59, from 12 :00 to 17 :59, and from 18 :00 to 23 :59, respectively.

Indeed, those values are smaller when compared with GeoLife results. That is due to the fact that 48% of days contained on OpenStreetMap dataset are on weekends, i.e., Saturday and Sunday, contrary to GeoLife that counts 27% of its days on weekends. Therefore, in this case, OpenStreetMap presents trajectories composed of mixed behaviors inherent from the dierences between working days and weekend days, e.g., people performing short routes going straight to work and people making longer routes roaming around while shopping.

Finally, it is important to understand whether the legs with low length ratio are performed by a small group of people or throughout a large group, i.e., "Is the usage of shortest paths an isolated tendency or a collective behavior ?". To do so, we calculate, for each period of the day, the cumulative percentage of users. Length ratio values were taken in steps of 0.5. For each step, we calculate the percentage of users who performed, at least, 50% of legs shorter than the step.

We calculate the percentage relative to the number of users on each period. Fig. 4 shows the cumulative percentage of users in function of the length ratio grouped by period of the day. For

Beijing, it shows that 67%, 75%, 66%, and 77% percent of the users perform mostly legs that are, at most, half longer than the shortest ones respectively for periods from 00 :00 to 05 :59, from 06 :00 to 11 :59, from 12 :00 to 17 :59, and from 18 :00 to 23 :59. Finally, for the same metric Tokyo presents 43%, 60%, 35% and 72% for periods from 00 :00 to 05 :59, from 06 :00 to 11 :59, from 12 :00 to 17 :59, and from 18 :00 to 23 :59. Therefore, the usage of shortest paths is indeed a collective behavior.

q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 00:00 -05: (a) Beijing q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 00:00 Inria q q q q q q q q q q q q q q q q q q q 0 10 20 Length ratio Cumulative number of users (%)

Period

q 00:00 -05:59 06:00 -11:59 12:00 -17:59 18:00 -23:59

(a) Beijing q q q q q q q q q q q q q q q q q q q 0 10 20

Discussion

Understanding human mobility behavior is a key aspect to develop better network services and solutions on several areas. This section discusses some applications that may benet from mobility aspects previously presented. Furthermore, GeoLife is a rich dataset suitable for studying routine-based services but has not been much explored in the literature. On the other hand, OpenStreetMap is still collaboratively building its GPS tracking dataset and it is not as rich as GeoLife in this aspect for any specic city.

Forwarding Protocols An important problem on Pocket Switched Networks area is how to couple human mobility patterns with message forwarding algorithms [START_REF] Hui | Pocket switched networks and human mobility in conference environments[END_REF]. Routinary behavior has been widely studied when it comes down to encounters among nodes. On the other hand, trajectories behavior could be studied to improve protocols based on store-and-forward late delivery. How far a person routinely goes or how frequently one visits the same places in a city could be important characteristics to dene the potential of a peer to be chosen to keep a message to be routed. For instance, the few percentage of people going routinely further than the 10km mark could be important routers on a Pocket Switched Network [START_REF] Han | Mobile data ooading through opportunistic communications and social participation[END_REF].

Social Hotspot Deployment Unplanned deployment of hotspots may lead to both underutilized and over-utilized network areas. The expansion of metropolitan areas increased the possibility of moving around. This fact together with the increase of smartphone use results in highly dynamic links, which may signicantly aect the performance of the network. Moreover, people may use dierent transportation modes, which signicantly impacts their trajectories. Mobilityoriented deployment may be an important point while projecting a network deployment. For instance, areas in which people frequently visit during their routinary behavior may be used as key areas to deploy a complementary network, e.g., WiFi hotspots providing data-ooading points for a 3G network [START_REF] Mucelli Rezende | Routine-based network deployment for data ooading in metropolitan areas[END_REF].

Routine-based Data Prefetching Prefetching has been shown to eectively reduce user perceived latency. An interesting approach might be to merge trajectory information with demanded content in order to provide a smart data prefetching approach. Based on the routine of person, a prefetching service could, for example, store static content of web pages visited often. This content could be downloaded using access points present in the places routinely visited by the person. For instance, an application for mobile phones could download content in advance at home using WiFi and this would be later presented along with content downloaded using 3G in real time. This approach could alleviate the usage of 3G by shifting to inexpensive networks (such as WiFi) the load of static content such as images.

Public Transportation Planning Monitoring, distributing, and processing trac information may enable better strategic planning and encourage better use of public transportation.

Several applications may take advantage of the driver's routinary behavior in order to improve aspects of the Vehicular Networks. For instance, trac information, e.g., accidents, construction sites, trac jams may be exchanged between vehicles. On a routinary scenario, all those information may be used to forecast the situation for the next days and alert the driver, for example, about possible alternative roads. Besides, a service may identify points of interest based on driver's mobility patterns. Identify parking lots and its availability in number of spots, or suggest the best charging station for electrical vehicles based on the driver's routine and battery conditions. Furthermore, a service to advertise products on roadside signs may merge dierent sources of information in order to display targeted marketing. By crossing information from the driver's routinary trajectories, trac condition and the driver's interests, a service could present ads that match driver's interest on a certain area of the city likely having the driver on its vicinity. On a collaborative scenario, a carpooling service could suggest people to get or to oer a ride based on regular driver's destinations and passengers interested on ride-sharing.

Conclusion

In this work, we have assessed the routinary behavior of people and pointed out means to explore it in order to provide better network services. We have studied a two real datasets representing together more than 2200 days from people's daily lives in Beijing and Tokyo. The results

show that people indeed tend to take shortest paths regardless the transportation mode and that it is a collective behavior, not a specic behavior of a certain group of people. In addition, people demonstrate more two characteristics on their mobility patterns : highly conned and repetitive trajectories. For instance, 83% and 95% of the trajectories for Beijing and Tokyo respectively, have at most, 10 km maximum displacement regardless the period of the day. Besides, on average, 70% of the trajectories are, at most, half longer than the shortest path regardless of the transportation mode. We have also presented (1) several network scenarios which might take advantage of those behaviors and (2) some possible ways to provide better network services on such scenarios. As future work, we envision to study routine-based deployment solutions with the purpose of providing a data-ooading architecture.

Figure 1

 1 Figure 1 CCDF of the maximum displacement.

Figure 2

 2 Figure 2 Heatmap of the Repetitiveness by grid cell (better seen in colors).

Figure 3

 3 Figure 3 CCDF of the length ratio by period.

Figure 4

 4 Figure 4 Percent of users as a function of the length ratio by period.

  Consulting the Table 1, it is possible to see that l

	Table 1 Average speed (m/s) ranges by transportation mode
	Transportation mode	Average speed range
	Walk	≤ 1.5
	Bus	> 1.5 and ≤ 4 [10]
	Bike or Run	> 4 and ≤ 4.4 [11]
	Taxi, Motorcycle, or Car	> 4.4 and ≤ 11.5 [12]
	Subway	> 11.5 and ≤ 28 [13]
	Train	> 28 and ≤ 250
	Airplane	> 250
	uniformly distributed number. In this example, l will be labeled either as 'taxi', 'motorcycle', or
	'car' with 33% of chance.
	falls on a range in which three transportation modes present overlapping average speed ranges,
	taxi, motorcycle, and car. Therefore, each one has equal chance of being chosen by a randomly
	1. http://wiki.openstreetmap.org/wiki/API_v0.6
		Inria

  100. Fig.2(better seen in colors) shows a heatmap by period of the day colored by repetitiveness values of each cell. This result depicts that repetitiveness is power-law distributed throughout the cells, i.e., while most of the cells receive few visits, few cells receive most of the visits. Indeed, 78%, 77%, 77% and 87% of the cells

in Beijing have, at most, 5% of repetitiveness (i.e., 5% of users revisited it) for periods from 00 :00 to 05 :59, from 06 :00 to 11 :59, from 12 :00 to 17 :59, and from 18 :00 to 23 :59, respectively. Besides, 0.4%, 0.2%, 0.2% and 0.2% of the cells in Beijing have more than 90% of repetitiveness for periods from 00 :00 to 05 :59, from 06 :00 to 11 :59, from 12 :00 to 17 :59, and from 18 :00 to 23 :59 respectively. People repetitively visit the same cells (high repetitiveness of trajectories shown previously), resulting in some few areas being highly popular, while most of the areas are unpopular. Regardless of the period of the day, a north central area consistently shows cells with hight repetitiveness, which is due to the fact that Microsoft Research Asia headquarter is located there. GeoLife experiment was conduced mostly with Microsoft members that were constantly walking nearby the working place.

Tokyo presents similar results, 76%, 75%, 72%, and 83% of its cells have, at most, 5% of repetitiveness for periods from 00 :00 to 05 :59, from 06 :00 to 11 :59, from 12 :00 to 17 :59, and from 18 :00 to 23 :59, respectively. On the other hand, 0.1%, 0.8%, 0.2%, and 0.07% of the cells have more than 90% of repetitiveness for periods from 00 :00 to 05 :59, from 06 :00 to 11 :59, from 12 :00 to 17 :59, and from 18 :00 to 23 :59 respectively. Two remarkable areas are presented on Tokyo's heatmap : (1) Kodaira Train Station on the northwest presents high repetitive from 06 :00 to 11 :59 and (2) Motosumiyoshi Station on the south highly active from 06 :00 to 11 :59 and from 12 :00 to 17 :59. Both present the characteristic of big train stations, high repetitive

RR n°8451

rue Honoré d'Estienne d'Orves Bâtiment Alan Turing Campus de l'École Polytechnique 91120 Palaiseau Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

* This work was supported by the EU FP7 ERANET program under grant CHIST-ERA-2012 MACACO.