Giorgio Ausiello
email: ausiello@dis.uniroma1.it

Aristotelis Giannakos
email: giannako@lamsade.dauphine.fr

Vangelis Th

Paschos
email: paschos@lamsade.dauphine.fr

On-line models for set-covering: the power of greediness

We study an on-line model for set-covering implying that elements of the ground set of size n arrive one-by-one and with any such element σ i , arrive also the names of the sets containing it in the final instance. Any new element has to be processed irrevocably before the arrival of the next element. We study limits on the competitiveness of several greedy rules solving several alternatives of this basic model. For any of them we give lower and upper bounds for the competitive ratio achieved. We finally deal with the maximum budget saving problem. Here, an initial budget is allotted that is destined to cover the cost of an algorithm for solving set-covering and the objective is to maximize the savings on the initial budget.

Introduction

Let C be a ground set of n elements and S a family of m subsets of C such that ∪ S∈S S = C. The set-covering problem consists of finding a family S ′ ⊆ S, of minimum cardinality, such that ∪ S∈S ′ S = C. In what follows, for an element σ i ∈ C, we set F i = {S j i ∈ S : σ i ∈ S j i } and f i = |F i |; also, we set f = max{f i : i = 1, . . . , n}.

The set-covering problem has been extensively studied over the past decades. It has been shown to be NP-hard in Karp's seminal paper ( [START_REF] Karp | Reducibility among combinatorial problems[END_REF]) and O(log n)-approximable for both weighted and unweighted cases (see [START_REF]A greedy-heuristic for the set covering problem[END_REF], for the former and [START_REF] Johnson | Approximation algorithms for combinatorial problems[END_REF][START_REF] Lovász | On the ratio of optimal integral and fractional covers[END_REF][START_REF] Slavík | A tight analysis of the greedy algorithm for set cover[END_REF], for the latter; see also [START_REF] Th | A survey how optimal solutions to some covering and packing problems can be approximated[END_REF] for a comprehensive survey on the subject). This approximation ratio is the best achievable, unless P = NP ( [START_REF] Raz | A sub-constant error probability low-degree test and a sub-constant error probability PCP characterization of NP[END_REF]).

In on-line computation, one can assume that the instance is not known in advance but it is revealed step-by-step. Upon arrival of new data, one has to decide irrevocably which of these data are to be taken in the solution under construction. The fact that the instance is not known in advance, gives rise to several on-line models specified by the ways in which the final instance is revealed, or by the amount of information that is achieved by the on-line algorithm at each step. In any of these models, one has to devise algorithms, called on-line algorithms, constructing feasible solutions whose values are as close as possible to optimal off-line values, i.e., to values of optimal solutions assuming that the final instance is completely known in advance. The closeness of an on-line solution to an optimal off-line one is measured by the so-called competitive ratio m(x, y)/ opt(x), where x is an instance of the problem dealt, y the solution computed by the on-line algorithm dealt, m(x, y) its value and opt(x) the value of an optimal off-line solution. This measure for on-line computation has been introduced in [START_REF] Sleator | Amortized efficiency of list update and paging rules[END_REF].

Informally, the basic on-line set-covering model adopted here is the following: elements of a ground set of size n arrive one-by-one and with any such element σ i (arriving during step i), arrive also something about some of the sets containing σ i . This "something" can be either the names of sets containing σ i or more information related to their cardinalities, or their covering potential, etc. At each step, σ i has to be processed immediately, i.e., it has either to be covered by some of the sets whose names has arrived with, or to be left uncovered risking so infeasibility of the final solution.

We first assume that together with an element the names of the sets containing it in the final instance are revealed. We show that if no further information is given, then the competitive ratio of any algorithm is Ω(n).

Next, we handle several algorithms dealing with the on-line model just sketched. The first one, called TAKE-ALL, takes at each step in the solution all the sets containing the element just revealed, if it is still uncovered. We show that this algorithm has tight competitive ratio O(f ), where f is the maximum number of sets in S that contain a ground element. The second algorithm, called TAKE-AT-RANDOM, is a randomized algorithm that at each step picks a set at random among the ones whose names are revealed an take it in the solution, if it is still uncovered. For this algorithm we provide an upper bound of O(n) for its competitiveness, as well as an asymptotically matching lower bound.

We then assume that together with the names of the sets covering a revealed element, an information concerning their covering potential is also communicated. We show that, in this case, the competitive ratio of any algorithm that, for any arriving uncovered element, takes in the cover at least one set containing it is bounded below by Ω( √ n). Assuming that the covering potential information given with any element is the name of the larger set containing it (in the final instance) we show that the competitive ratio of the greedy algorithm, called TAKE-LARGEST, consisting of taking this set in the solution is O(n) and that it is tight. We next address the following question: "what an on-line algorithm must know about sets in order to guarantee an upper competitive bound of O( √ n)?" We show that such a bound can be attained at least by an algorithm, called TAKE-LARGEST-ON-FUTURE-ITEMS, which at any step i takes some set containing σ i covering the most of the ground set-elements that have not been yet covered (clearly, any uncovered element is yet unrevealed). This assumption can be seen as the on-line counterpart of the natural greedy (off-line) set-covering algorithm, called GREEDY in what follows. We recall that this algorithm takes in the solution a set covering the most of the still uncovered elements.

Finally, we address a budget variant of set-covering. We assume that two algorithms collaborate to solve the problem. The application-cost of the former is just the cardinality of the solution it finally computes, while, for the latter, its application cost is the cardinality of its solutions augmented by an overhead due, for example, to the fact that it is allowed to wait before making its decisions. We can see the application cost of the former algorithm as a kind of budget allotted to them that is not allowed to be overcome. The objective is to perform the maximum possible saving upon the initial budget. We show that there exists a natural algorithm-cost model such that GREEDY is asymptotically optimal for maximum budget saving when the budget allotted is the application cost of TAKE-LARGEST-ON-FUTURE-ITEMS.

The remainder of this paper is organized as follows. In Section 2, we describe the main result presented in the paper more in detail and we compare our approach to other approaches introduced in the literature. Section 3 is devoted to a general competitiveness lower bound for simple on line algorithms. In Section 4, we present two simple algorithms, TAKE-ALL and TAKE-AT-RANDOM and we discuss their performances. In Sections 5 and 6 the power of look ahead is discussed, first by showing that any algorithm that knows the covering potential of the sets which contain a revealed (not covered) item cannot attain a competitive ratio better than Ω( n/2) and then by exhibiting an algorithm whose competitive ratio matches such bound. Section 7 is devoted to the budget version of the problem. Finally, in Section 8, conclusive issues are discussed.

Description of the main results and related work

In [START_REF] Alon | The online set cover problem[END_REF], the following on-line set-covering model has been studied. We suppose that we are given an instance (S, C) that it is known in advance, but it is possible that only a part of it, i.e., a sub-instance (S p , C p ) of (S, C) will finally arrive; this sub-instance is not known in advance. A picturesque way to apprehend the model is to think of the elements of C as lights initially switched off. Elements switch on (get activated) one-by-one. Any time an element c gets activated, the algorithm has to decide which among the sets of S containing c has to be included in the solution under construction (since we assume that (S, C) is known in advance, all these sets are also known). In other words, the algorithm has to keep an online cover for the activated elements. The algorithm proposed for this model achieves competitive ratio O(log n log m) (even if less than n elements of C will be finally switched on and less than m subsets of S include these elements).

The on-line model dealt here is inspired (yet quite different since it does not allow that, once arrived, an element can disappear) from the one in [START_REF] Alon | The online set cover problem[END_REF]. Moreover, and most important, the instance (S, C) is not known in advance. In our model, we are given an arrival sequence Σ = (σ 1 , . . . , σ n ) of the elements of C (i.e., elements of C are switched on following the order σ 1 , . . . , σ n ), the objective is to find, for any i ∈ {1, . . . , n}, a family S ′ i ⊆ S such that {σ 1 , . . . , σ i } ⊆ ∪ S∈S ′ i S. Recall that for any σ i , i = 1, . . . , n, we denote by F i = {S j i : S j i ∈ S, σ i ∈ S j i } the sets of S containing σ i , by f i the cardinality of F i , usually called frequency, and we set f = max σ i ∈Σ {f i }. We denote by Sj i the subset of the elements of S j i ∈ F i still remaining uncovered and by δ j i the cardinality of Sj i . When σ i switches on, something about sets in F i , j = 1, . . . , f i is revealed. We first assume that this "something" is the names of the sets covering σ i , i.e., the names in F i . We show that, if no further information is supplied, then no on-line algorithm can achieve competitive ratio better than O(n).

We then study the competitiveness of two algorithms dealing with this model, namely TAKE-ALL and TAKE-AT-RANDOM.

The former, any time some σ i arrives, if it is still uncovered, i.e., if none of the sets taken in the solution up-to-date does belong to F i , then takes all the sets in F i in the solution under construction. We show that the competitive ratio of TAKE-ALL is bounded above by f , the maximum frequency of the final instance, and that this ratio is tight and can be even exponential with n.

In the case of TAKE-AT-RANDOM, any time some σ i arrives, if it is still uncovered, the algorithm picks at random a set in F i and puts it in the solution. We show that its competitive ratio is bounded above by O(n). We also prove that its expected competitive ratio cannot be better than O(n 1-(1/ǫ) ), for any ǫ > 0. We so have a lower bound that asymptotically matches its competitive ratio.

We next assume that together with F i , some more information is revealed about the covering potential of some of the sets in F i . We show that under this assumption, no on-line algorithm that, upon the arrival of an uncovered element, processes it by adding to the cover at least one set containing it can guarantee competitive ratio better than n/2. Furthermore, we show that if together with F i the name of some set Ŝi ∈ argmax{|S j i |, j = 1, . . . , f i } is revealed, then the greedy rule (called TAKE-LARGEST, in the sequel) that if σ i is still uncovered, takes Ŝi in the solution, achieves competitive ratio O(n).

The two results mentioned just above show that there is an important gap between the general lower bound of n/2 and the ratio achieved by TAKE-LARGEST. Hence, a question rises naturally: "what an on-line algorithm must know in order to achieve a ratio closer to this bound, say O( √ n), respecting always the given on-line model? We show that there exists at least an implementation doing this, if it owns some look-ahead informations.

We show that if together with σ i and F i , the name of some set Si ∈ argmax{δ j i , j = 1, . . . , f i }, i.e., the name of a set in F i covering the most of the still unrevealed elements is revealed, then the greedy rule (TAKE-LARGEST-ON-FUTURE-ITEMS) that adds Si in the cover, if σ i remains still uncovered, achieves tight competitive ratio O( √ n). Let us note that TAKE-LARGEST-ON-FU-TURE-ITEMS is a kind of on-line analogue of GREEDY. Hence, analysis of its competitiveness is interesting by its own.

Note also that a basic and very interesting feature of the introduced models is their small memory requirements, since the only information needed is the binary encoding of the names of the sets. This is a major difference between our approach and the one of [START_REF] Alon | The online set cover problem[END_REF]. There, anytime an element gets activated, the algorithm needs to compute the value of a potential function using an updated weight parameter for each element and then chooses covering sets in a suitable way so that this potential be non-increasing; the greedy online algorithm in our model needs only a constant number of memory places, making it more appropriate for handling very large instances with very few hardware ressources. For instance, the rules used here use at most O(m) space.

We are so faced to the power (rather the weakness) of greediness. Let us recall that the on-line models that we consider assume no knowledge of the topology of the final instance (S, C) and immediate processing of any arriving element σ i . Obviously, the rules that we consider are the only to feasibly solve the problem in such situations. Furthermore they are very efficient in time and in memory requirements, hence well adapted to face really on-line practical situations. On the other hand, since no a priori knowledge of instance's topology is admitted, no algorithm can do complex preliminary calculations (as the potential calculations in [START_REF] Alon | The online set cover problem[END_REF]) in order to judiciously choose the set to be included in the cover under construction.

In many real-life problems, it is meaningful to relax the main specification of the online setting, that is, to keep a solution for any partially revealed instance, in order to achieve a better solution quality. In this sense, a possible relaxation is to consider that several algorithms collaborate in order to return the final solution. The costs of using these algorithms can be different the ones from the others, depending upon the sizes of the solutions computed, the time overheads they take in order to produce them, etc. Moreover, we can assume that an initial common budget is allotted to all these algorithms and that this budget is large enough to allow use of at least one of the algorithms at hand to solve the problem without exceeding it. A nice objective could be in this case, to use these algorithms in such a way that a maximum of the initial budget is saved.

For the case of set-covering, the following budget-model, giving rise to what we call maximum budget saving problem is considered in Section 7. We assume that two algorithms collaborate to solve it: say TAKE-LARGEST-ON-FUTURE-ITEMS and the greedy (off-line) algorithm. The application-cost of the former is just the cardinality of the solution it finally computes, while, for the latter, its application cost is the cardinality of its solutions augmented by an overhead due, for example, to the fact that it is allowed to wait before making its decisions. For an instance x of set-covering, the initial budget considered is B(x) = √ n opt(x) (this is in order that at least TAKE-LARGEST-ON-FUTURE-ITEMS is able to compute a solution of x without exceeding the budget for any x). Denote by c(x, y) the cost of using A in order to compute a cover y for x.

The objective is to maximize the quantity B(x)c(x, y) and, obviously, the maximum possible economy on x is B(x)opt(x). We show in Section 7 that there exists a natural algorithm-cost model such that GREEDY is asymptotically optimal for maximum budget saving.

Before closing this section, let us quote another approach that could be considered to be at midway between semi-on-line and reoptimization approaches, developed in [START_REF] Gambosi | Preserving approximation in the min-weighted set cover problem[END_REF]. There, the problem tackled is the maintenance of approximation ratio achieved by an algorithm while the set-covering instance undergoes limited changes. More precisely, assume that a set-covering instance (S, C) and a solution S ′ for it are given. How many insertions of some of the ground elements in subsets that did not previously contain these elements produce an instance for which the solution S ′ of the initial instance guarantees the same approximation ratio in both of them? In [START_REF] Gambosi | Preserving approximation in the min-weighted set cover problem[END_REF] it is shown that if solution S ′ has been produced by application of the natural greedy algorithm achieving approximation ratio O(log n) ( [START_REF]A greedy-heuristic for the set covering problem[END_REF]), then after O(log n) such insertions initial solution S ′ still guarantees the same approximation ratio. In the same spirit lies also the similar set-covering model in [START_REF] Telelis | Dynamic maintenance of approximate set covers[END_REF].

The price of ignorance

In this section we consider the first version of the on-line model sketched in Section 2. Assume an arrival sequence Σ = (σ 1 , . . . , σ n ) of the elements of C, and the objective is to find, for any i ∈ {1, . . . , n}, a family

S ′ i ⊆ S such that {σ 1 , . . . , σ i } ⊆ ∪ S∈S ′ i S.
Once an element σ i , i = 1, . . . , switches on, only the encodings of the members of F i are also revealed.

For this case we first prove that when no additional information is given, any rule that has to cover a new element without any look-ahead behaves rather badly. In this sense strategies that choose elements either randomly or based upon observations of the past (for instance take the subset that has appeared the most frequently or the most rarely until now) are highly inefficient.

Proposition 1. If no information is given about the sets revealed with an arriving not covered ground element, then the competitive ratio of implementation of any greedy principle is Ω(n)

Proof. The adversary reveals a first uncovered element along with the names S 1 , . . . , S N of N sets covering it in the final instance. He then keeps revealing uncovered elements along with all sets from S 1 , . . . , S N not already taken into the cover, until the algorithm has taken all N sets into the cover.

Suppose w.l.o.g. that the algorithm has taken S 1 , . . . , S l 1 , S l 1 +1 , . . . , S l 2 , S l 2 +1 , . . . , S l 3 , and at the kth and final step, S l k-1 +1 , . . . , S l k = S N .

The adversary can give the following interpretation to the instance: S = {S 1 , . . . , S N }. There are n = log N + k ground elements, namely {σ 1 , . . . , σ log N , 1, . . . , k} (notice also that k N ). The set S i taken at step j contains the elements σ p , for all places p where the binary expression of i has an 1, plus elements in {1, . . . , j}. The arrival sequence is 1, . . . , k.

In this interpretation, the set S N , taken at the last step, is the ground set itself; thus, in such a setting, the competitive ratio of the algorithm would be N , i.e., Ω(n)

It can be immediately seen that under the given model, any deterministic algorithm that takes a specific set containing a new (uncovered) element σ i (for example, the set of F i that comes first in lexicographic order) achieves competitive ratio O(n). Indeed, it chooses at most n sets for an optimum greater than, or equal to 1.

Competitiveness of TAKE-ALL and TAKE-AT-RANDOM

Algorithm TAKE-ALL

Recall that algorithm TAKE-ALL, whenever a newly revealed element σ i is not already covered by sets already taken in the solution due to former arrivals, it takes in the solution the whole family F i the names of the members of which have been revealed together with σ i . Proposition 2. The competitive ratio of TAKE-ALL is bounded above by f . This ratio is tight.

Proof. Denote by σ 1 , . . . , σ k the critical elements of Σ, i.e., the elements having entailed the introduction of S 1 , . . . , S k in S ′ . Denote also by S * an optimum off-line solution. Obviously, for any of the critical elements, a distinct set is needed to cover it, in any feasible cover for C; hence:

|S * | k (1)
On the other hand, since, for i = 1, . . . , k, f i f :

S ′ kf (2)
Combining ( 1) and ( 2), the competitive ratio is immediately derived.

In order to show tightness, consider an instance with ground set C = {1, . . . , n} and the family of all 2 n-1 sets formed by 1 union any other set in 2 C\{1} . With an arrival sequence starting with 1, the competitive ratio of TAKE-ALL would be 2 n-1 = f . Note that TAKE-ALL is similar to the approximation algorithm for minimum set-covering presented in [START_REF] Hochbaum | Approximation algorithms for the set covering and vertex cover problems[END_REF] and, furthermore, it guarantees the same approximation ratio.

Note also that, from Proposition 2, TAKE-ALL gives a much worse competitiveness than n.

Algorithm TAKE-AT-RANDOM

Recall that TAKE-AT-RANDOM chooses at random one set in F i per revealed uncovered element σ i and puts it in the solution. It can be immediately seen that, with the same arguments as the ones at the end of Section 3, TAKE-AT-RANDOM achieves competitive ratio O(n). In the following proposition, we show that even its expected competitive ratio, if it chooses one of the sets covering σ i with uniform probability, cannot be much better than O(n).

Theorem 1. For any ǫ > 0, there exists an instance of the on-line set-covering with n ground elements such that the expected competitive ratio of TAKE-AT-RANDOM is Ω(n 1-(1/ǫ) ).

Proof. For any ǫ > 0, fix an integer k > 1/ǫ and let N > 2 k . Consider the instance with ground set C = {1, . . . , n = N k }. Family S contains the following sets:

• a partition of class sets S(i) = {j ∈ C : (j -1) ÷ N = (i -1)}; clearly, |S(i)| = N and there exist N k-1 class sets;

• for any j ∈ S(i) for some i, there exist 2 N -1 internal sets, each one containing j plus the elements of one of all possible subsets of S(i) (including the empty set);

• the ground set C itself.

Consider now an arbitrary arrival sequence, and compute the expected value of the cover, which will be equal to the expected competitive ratio of TAKE-AT-RANDOM (equality holds, since the optimum for this instance is C).

Every element belongs to one class set and to 2 N -1 internal sets. We note by E(q) the expected value of TAKE-AT-RANDOM on the instance of q elements defined as before. Then:

E N k = 1 2 N -1 + 1 1 + N -1 l=0 N -1 l 1 + E N k -l -1 ≥ 1 2 N -1 + 1 1 + 2 N -1 + 2 N -1 E N k -N ≈ 1 + E N k -N
The recursive relation yields then directly

E(N k ) ≥ N k-1 , i.e., E(n) = Ω(n 1-(1/ǫ) ).
Example 1. We now give an example of construction of Theorem 1. Consider N = 3 and k = 3 (these values of N and k are not conformal with their definition but, in a first time, we use them for simplicity). Then C = {1, 2, . . . , 27} and we have:

• class sets: {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}, {13, 14, 15}, {16, 17, 18}, {19, 20, 21}, {22, 23, 24} and {25, 26, 27};

• for any class set {a, b, c}, there exist the internal sets: {a}, {b}, {c}, {a, b}, {a, c} and {b, c};

• finally C = {1, 2, . . . , 27} ∈ S.

Let us assume that σ 1 = 17. With it will be revealed the following 2 2 + 1 = 5 sets: {17}, {17, 18}, {17, 19}, {17, 18, 19} and {1, 2, . . . , 27}. The average cover for the whole instance will be of size 9, independently on the arrival sequence. Indeed, for k = 3, N 8. Taking N = 8, n = 512. In this case, the class sets would be the partition of {1, 2, . . . , 512} into 64 subsequent 8-tuples. For any class set there would be 254 internal sets. With any element of the arrival sequence they would arrive 1 class set, plus 63 internal sets plus set {1, 2, . . . , 512}, i.e., 8 3-1 + 1 = 65 sets. The average cover size would be in this case 64.

The nasty flaw of greediness

In this section, we consider a slightly enriched model for on-line set-covering by assuming that together with any element σ i of the arrival sequence, arrive not only the names of the sets containing them to the final instance but also some information about the cover potential of some of these sets.

In what follows, we show that, even for this revised model, no on-line algorithm can achieve competitive ratio better than n/2, even if it is allowed to choose at any step more than one set to be introduced in the solution.

Theorem 2. Consider an on-line model for set-covering where together with any element σ i of the arrival sequence, arrive not only the names of the sets containing them to the final instance but also some information about the cover potential of some of these sets. Then, on-line algorithm for this model such that, at any step, it takes in the cover at least one set containing some not yet covered arriving element can achieve competitive ratio less than n/2, even if one assumes that with any σ i , Si is also revealed.

Proof. Consider the following set-covering instance built, for any integer N , upon a ground set S = {x ij : 1 j i N }; obviously, |C| = n = N (N + 1)/2. A path-set of order i is defined as a set containing Ni + 1 elements {x ij i , . . . , x N j N }. The set-system S of the instance contains all possible path-sets of each order i, 1 i N . Clearly, there exist N !/0! path-sets of order 1, N !/1! of order 2, and so on and, finally, N !/(N -1)! path-sets of order N , i.e., in all N !(1 + . . . + 1/(N -1)!) ≈ eN ! path-sets. Finally, the set-system S is completed with an additional set Y containing all elements of C but those of some path-set of order 1, that will be specified later (hence, |Y | = n -N ).

As long as there exist uncovered elements, the adversary may choose to have an uncovered element x ij of the lowest possible i arriving, which will be contained only in all path-sets of order less than or equal to i. Notice that as long as algorithm A has r < N sets inserted in the cover, there will be at least one element x (r+1)j for some j, 1 j k + 1, yet covered. Suppose that after the arrival of σ t , the size of the cover computed by A gets equal to, or greater than, N . Clearly, 1 t N . At time t + 1, a new element arrives, contained in some path-sets and in Y , which can be now specified as consisting of all elements in C except of the elements of some path-set S * of order 1 containing σ 1 , . . . , σ t ; the rest of the arrival sequence is indifferent.

Clearly the optimum cover in this case would have been path-set S * together with set Y ; hence, k A /k * N/2, with N tending to √ 2n as n increases. It is easy to see that the above construction can be directly generalized so that the same result holds also in the case that the on-line algorithm is allowed to take more than one sets at a time in the cover: if σ 1 = x 11 , then as long as the size of the online cover is less than N , there exists always some i ℓ-1 < i ℓ N and some j i ℓ for which x i ℓ j i ℓ is yet uncovered. Hence, if σ ℓ is this element, then the algorithm will have to put some sets in the cover. Finally, the algorithm will have put N sets in the cover, while the optimum will always be of size 2.

(1,1)

(2,1) Example 2 . In order to illustrate the construction in Theorem 2, consider the instance of 1, with N = 5 (the elements of C are depicted as cycles labelled by (i, j) for 1 j i 3). The S i sets can be thought of as paths terminating to a sink on the directed graph of Figure 1(a). Assume that (1, 1) and algorithm A chooses sets {(1, 1), (2, 1), (3, 1)}, {(1, 1), (2, 2), (3, 2)} for covering it; the uncovered element (3, 3) arrives next, so A has to cover it by, say, the set {(2, 1), (3, 3)} (Figure 1(b)). The optimal cover might consist of set {(1, 1), (2, 2), (3, 3)} together with a big set consisting of the rest of the elements, that could not have been revealed to A upon arrival of (1, 1), or of (3, 3) (Figure 1(c)).

(3,1) (2,2) (3,2) (3,3) (a) (1,1) (2,1) (3,1) (2,2) (3,2) (3,3) (b) (1,1) (2,1) (3,1) (2,2) (3,2) (3,3) (c)
Let us now see what is the situation if we assume that together with F i is also revealed the name of some set Ŝi ∈ argmax{|S j i |, j = 1, . . . , f i } and we implement TAKE-LARGEST that consists of taking Ŝi in the solution.

Observe first that the discussion about the competitiveness of deterministic algorithms that take a specific set containing a new (uncovered) element, holds also for TAKE-LARGEST. Hence its competitive ratio is bounded above by n. We now show that this ratio is asymptotically tight.

Consider the following set-covering instance: a ground set C = {1, . . . , 2N }, a family of sets S = {S 0 , . . . , S N } with S i = {i, . . . , N + i}. Assume an arrival sequence starting with N, N + 1, . . . , 2N . Then, TAKE-LARGEST, might take into the cover sets S 1 , . . . , S N , while the optimum cover would be consisting of only S 0 , S N , thus yielding a competitive ratio of N/2.

The power of look-ahead

The discussion in Section 5 shows a large gap between the lower bound provided for any algorithm this model in Theorem 2 and the (tight) competitiveness of TAKE-LARGEST, that is one of the most natural rules one could think about. So, an immediate question can be addressed: "what an on-line algorithm has to know in order to achieve a competitive ratio O( √ n)? is it possible to devise such an algorithm?" The following result tackles these questions.

Theorem 3. Consider an instance (S, C) of minimum set-covering with |C| = n. Assume an arrival sequence Σ = (σ 1 , . . . , σ n ) and suppose that once an element σ i , i = 1, . . . , switches on, the encoding for Si ∈ argmax{δ j i , j = 1, . . . , f i } is also revealed together with . Consider implementation of TAKE-LARGEST-ON-FUTURE-ITEMS that, if σ i is not already covered in one of the previous steps, it takes Si in the solution under construction. Denote by S * = {S * 1 , . . . , S * k * } an optimal off-line solution on (S, C). Then, the competitive ratio of TAKE-LARGEST-ON-FUTURE-ITEMS is bounded above by min{ 2n/k * , √ n}. Furthermore, there exist large enough instances for which this ratio is at least n/2.

Proof. Fix an arrival sequence Σ = (σ 1 , . . . , σ n ) and denote by c 1 , . . . , c k , its critical elements, i.e., the elements having entailed introduction of a set in S ′ . In other words, critical elements of Σ are all elements c i such that c was not yet covered by the cover under construction upon its arrival. Assume also that the final cover S ′ consists of k sets, namely, S 1 , . . . , S k , where S 1 has been introduced in S ′ due to c 1 , S 2 due to c 2 , and so on.

Let δ(S i ) be the increase of the number of covered elements just after having taken S i in the greedy cover (recall that if S i has been added in S ′ for critical element c i = σ j , δ(S i ) = max{δ 1 j , . . . , δ f j j }). We have:

δ (S 1 ) = |S 1 | (3)
δ (S i ) = i ℓ=1 S ℓ - i-1 ℓ=1 S ℓ , 2 i k (4)
Fix now an optimal off-line solution S * of cardinality k * . Any of the critical elements c 1 , . . . , c k can be associated to the set of smallest index in S * containing it. For any S * i ∈ S, we denote by Ŝ * i , the set of the critical elements associated with S * i (obviously, Ŝ * i ⊆ S * i ). The critical content h(S * i ) of any S * i ∈ S * is defined as the number of critical elements associated to it as described before, i.e., h(

S * i ) = | Ŝ * i |. Let S *
1 , . . . , S * r be the sets in S * of positive critical contents h(S * 1 ), . . . , h(S * r ), respectively. Clearly,

r i=1 h (S * i ) = k (5) r k * (6)
For any S * i , let c 1 i , . . . , c h(S * i ) i be the elements of its critical content ordered according to their position in the arrival sequence Σ; in other words, following our assumptions, Ŝ *

i = {c 1 i , . . . , c h(S * i ) i } (recall that Ŝ * i ⊆ S * i ).
Suppose, without loss of generality, that, for ℓ = 1, . . . , h(S * i ), the set S j ℓ ∈ S has been introduced in S ′ when the critical element c ℓ i has been activated. At the moment of the arrival of c 1 i , the set S * i is also a candidate set for S ′ . The fact that S j 1 has been chosen instead of S * i means that δ(S j 1 ) δ(S * i ); hence, since as noticed just above, Ŝ * i ⊆ S * i , the following holds immediately:

δ(S j 1 ) δ(S * i ) | Ŝ * i | = h(S * i ). When c 2
i gets activated, the set S * i has lost some of its elements that have been covered by some sets already chosen by the algorithm. In any case, it has lost c 1 i (covered by S j 1 ). So, following the arguments developed just above for S j 1 , δ(S j 2 ) h(S * i ) -1, and so on (quantities δ(•) are defined either by (3), or by (4)). So, dealing with c ℓ i , the following holds:

h (S * i ) -ℓ + 1 δ (S j ℓ ) (7)
For example, consider the illustration of Figure 2. Let S * be a set of the fixed optimal cover S * and denote by Ŝ the set of its critical elements, c 1 , c 2 and c 3 (ranged in the order they have been activated). Let S be the set chosen by TAKE-LARGEST-ON-FUTURE-ITEMS to cover c 2 . The shadowed parts of S * , Ŝ and S correspond to elements already covered by TAKE-LARGEST-ON-FUTURE-ITEMS at the moment of arrival of c 2 . At this moment, S must contain at least as many uncovered elements as S * does and a fortiori at least one uncovered element for any yet uncovered critical element of S * (two uncovered elements S appear below the dashed line for c 3 and c 4 ). Summing up inequalities [START_REF] Lovász | On the ratio of optimal integral and fractional covers[END_REF], for ℓ = 1, . . . , h(S * i ), and setting

S Ŝ S * c 1 c 2 c 3 c 4
h(S * i )
ℓ=1 δ(S j ℓ ) = n i , we finally get for S i :

h (S * i ) (h (S * i ) + 1) 2 h(S * i ) ℓ=1 δ (S j ℓ ) = n i =⇒ h (S * i ) √ 2n i (8)
Set, for 1 i r, n i = α i n, for some

α i ∈ [0, 1]. Then, r i=1 α i = 1 and r i=1 √ α i √ r (9)
Using ( 5), ( 6), ( 8) and ( 9), we get:

k = r i=1 h (S * i ) √ 2n r i=1 √ α i √ r √ 2n √ k * √ 2n (10)
Dividing the first and the last members of (10) by k * , we get:

k k * 2n k * (11)
On the other hand, remark that, if k * = 1, i.e., if there exists S * ∈ S such that S * = {S * }, then TAKE-LARGEST-ON-FUTURE-ITEMS would have chosen it from the beginning of its running in order to cover σ 1 ; next, no additional set would have entered the S ′ . Consequently, we can assume that k * 2 and, using [START_REF] Sleator | Amortized efficiency of list update and paging rules[END_REF],

k k * √ n (12)
Combination of ( 11) and ( 12) concludes the competitive ratio claimed. Fix an integer N and consider the following instance (S, C) of minimum set-covering:

C = 1, . . . , N (N + 1) 2 S 1 = {1, . . . , N } S 2 = {N + 1, . . . , 2N -1} . . . S N = N (N + 1) 2
S N +1 = (i 1)N - i(i -3) 2 : i = 1, . . . , N S N +2 = C \ S N +1
Consider the arrival sequence (1, . . . , N (N + 1)/2). TAKE-LARGEST-ON-FUTURE-ITEMS might compute the cover S ′ = {S i , 1 i N }, while the optimal one is S * = {S N +1 , S N +2 }. Hence, the competitive ratio in this case would be N/2, with N = (-1 + √ 1 + 8n)/2 which is asymptotically equal to n/2 as claimed. For example, consider Figure 3. If Σ starts with 1, 6, 10, 13, 15, TAKE-LARGEST-ON-FUTU-RE-ITEMS may have chosen sets {1, 2, 3, 4, 5}, {6, 7, 8, 9}, {10, 11, 12}, {13, 14}, {15}, respectively, while the optimal cover would consist of sets {1, 6, 10, 13, 15} and {2, 3, 4, 5, 7, 8, 9, 11, 12, 14}. The proof of the theorem is now complete.

Revisit [START_REF] Sleator | Amortized efficiency of list update and paging rules[END_REF], set ∆ = max S i ∈S {|S i |} and take into account the obvious inequality: k * n/∆. Then, the following result is immediately derived from Theorem 3.

Corollary 1 .

The competitive ratio of TAKE-LARGEST-ON-FUTURE-ITEMS is bounded above by √ 2∆.

It can be easily seen from the proof of Theorem 3 that it also works even if one assumes that the arrival sequence does not contain all the elements of C but only a part of them. In this case, the competitive ratio achieved is 2n/k * √ 2n, since the hypothesis on the size of k * (discussed at the end of the of Theorem 3) is no more valid. This is important for TAKE-LARGEST-ON-FUTURE-ITEMS because it can be seen as an algorithm working also for the on-line model in [START_REF] Alon | The online set cover problem[END_REF] with provably upper competitive bound.

Corollary 2. The competitive ratio of TAKE-LARGEST-ON-FUTURE-ITEMS when assumed that only a subset of C will finally be revealed is bounded above by √ 2n.

The counter-example given in the proof of Theorem 3 can be slightly modified to fit the case where, at each step, whenever a yet uncovered element arrives, the algorithm is allowed to take in the cover a constant number of sets containing it and such that the number of elements yet switched off that belong to these sets is maximized. Let Proof. For some ρ > 1 and for some integer N , consider the following instance:

F [ρ] i = argmax{| Sj 1 i ∪ Sj 2 i ∪. . .∪ Sjρ i | : S j 1 i , S
S = X, Y, S j i : 1 i N, 1 j ρ C = N i=1 ρ j=1 S j i |C| = ρ N (N -1) 2 + N = n X = {x 1 , . . . , x N } S j i = N -i + 1 for i = 1, . . . , N S j i S k l = ∅, if i = l S j i S k i = {x i } , if j = k Y = C \ X
Consider the arrival sequence where x 1 , . . . , x N are firstly revealed. TAKE-LARGEST-ON-FUTU-RE-ITEMS might take in the cover all the S j i 's, while the optimal cover is {X, Y }. In this case, the competitive ratio is ρN /2, with:

N = ρ -2 2ρ + ρ -2 2ρ 2 + 2 n ρ
i.e., the value of the ratio is asymptotically ρn/2. For example, set ρ = 2 and N = 5 and consider the instance of Figure 4. For Σ starting with x 1 , x 2 , x 3 , x 4 , x 5 , the algorithm may insert to the cover the sets depicted as "rows", while the optimal cover would consist of the "column"-set {x 1 , x 2 , x 3 , x 4 , x 5 } together with the "big" set containing the rest of the elements (drawn striped in Figure 4).

Finally, let us note that one cannot do better if a rule concerning the already covered elements is added; the arrival sequence can be set in such a way that always arrive elements not yet covered, until the greedy online cover reaches all elements. In the weighted version of set-covering, any set S of S is assigned with a non-negative weight w(S), and a cover S ′ of the least possible total weight W = S∈S ′ w(S) has to be computed. A natural modification of TAKE-LARGEST-ON-FUTURE-ITEMS in order to deal with weighted set-covering is to put in the cover, whenever a still uncovered element arrives, a set S i containing it that minimizes the quantity w(S i )/δ(S i ). Unfortunately, this modification cannot perform satisfactorily. Consider, for example, an instance of weighted set-covering consisting of a ground set C = {x 1 , . . . , x n }, and three sets, S = C with w(S) = n, X = {x 1 } with w(X) = 1 and Y = C \ {x 1 } with w(Y ) = 0. If x 1 arrives first, the algorithm could have chosen S to cover it, yielding a cover for the overall instance of total weight n, while the optimal cover would be {X, Y } of total weight 1.

✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✂ ✁✂

The maximum budget saving problem

In this section, we study a kind of dual version of the minimum set-covering, the maximum budget saving problem. Here, we are allotted an initial budget B(S, C) destined to cover the cost of an algorithm that solves minimum set-covering on (S, C). Any such algorithm has its own cost that is a function of the size of the solution produced, of the time overheads it takes in order to compute it, etc. Our objective is to maximize our savings, i.e., the difference between the initial budget and the cost of the algorithm. For simplicity, we assume that the maximum saving ever possible to be performed is B(S, C)k * , where, as previously, k * is the size of an optimum set-cover of (S, C).

We consider here that the set-covering instance arrives on-line. If a purely on-line algorithm is used to solve it, then its cost equals the size of the solution computed; otherwise, if the algorithm allows itself to wait in order to solve the instance (partly or totally) off-line then, its cost is the sum of the size of the solution computed plus a fine that is equal to some root, of order strictly smaller than 1, of the solution that would be computed by a purely on-line algorithm. We suppose that the budget allotted is equal to k * √ n, where n = |C|. This assumption on B(S, C) is quite natural. It corresponds to a kind of feasible cost for an algorithm; we assume that this algorithm is TAKE-LARGEST-ON-FUTURE-ITEMS, the best among the ones seen in the paper.

The interpretation of this model is the following. We are allotted a budget corresponding to the cost of an algorithm always solving set-covering. In this way, we are sure that we can always construct a feasible solution for it. Furthermore, by the second part of Theorem 3, it is very risky to be allotted less than k * √ n since there exist instances where the bound √ n is attained. On the other hand, we can have at our disposal a bunch of on-line or off-line algorithms, any one having its proper cost as described just above, from which we have to choose the one whose use will allow us to perform the maximum possible economy with respect to our initial budget. The fact that the measure of the optimum solution for maximum budget saving is B(S, C)k * , has also a natural we can assume that there exist an arrival sequence Σ for C such that, for any σ i ∈ Σ, an oracle can always choose to cover σ i with the same set with which σ i is covered in an optimum off-line solution for instance (S, C). Under this assumption for the measure of the optimum budget saving solution, this problem is clearly NP-hard since it implies computation of an optimum solution for minimum set-covering. Finally, denoting by c A (S, C) the cost of algorithm A when solving minimum set-covering on (S, C), the approximation ratio of maximum set saving is equal to:

B(S, C) -c A (S, C) B(S, C) -k * (13)
Obviously this ratio is smaller than 1 and, furthermore, the closer the ratio to 1, the better the algorithm it.

Theorem 4. Under the model adopted, GREEDY is asymptotically optimum for maximum budget saving.

Proof. Consider an instance (S, C) of minimum set-covering and denote by k F and k L , the sizes of the solutions computed by algorithms GREEDY and TAKE-LARGEST-ON-FUTURE-ITEMS, respectively. By what has been assumed just above, denoting by c F the cost of using GREEDY, there exist some ǫ > 0 such that:

c F (S, C)) = k F + k 1-ǫ L (14)
Moreover, the following inequalities hold, the first one from [START_REF] Slavík | A tight analysis of the greedy algorithm for set cover[END_REF] and the second one from Theorem 3:

k F k * log n (15) k L k * √ n (16)
Using ( 14), ( 15) and ( 16), we get the following inequality for c F (S, C)):

c F (S, C)) k * 1-ǫ n 1-ǫ 2 + k * log n n 1-ǫ 2 + log n k * (17)
On the other hand, as assumed above:

B(S, C) = k * √ n (18)
Using (13), ( 17) and (18), we obtain:

B(S, C) -c F (S, C) B(S, C) -k * k * √ n -n 1-ǫ 2 + log n k * k * √ n -k * = √ n -n 1-ǫ 2 + log n √ n -1 (19)
It is easy to see that, for n large enough, the last term of (19) tends to 1, and the statement claimed by the theorem is true.

Figure 1 :

 1 Figure 1: The counter-example of Theorem 2 for N = 5.

Figure 2 :

 2 Figure 2: An example for (7).

Figure 3 :

 3 Figure 3: The ratio n/2 for TAKE-LARGEST-ON-FUTURE-ITEMS is asymptotically attained.

Figure 4 :

 4 Figure 4: A counter-example for the case where the algorithm is allowed to take a constant of sets containing a recently arrived element.

  ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂ ✁✂

	x 1
	x 2
	x 3
	x 4
	x 5

Remark also that if we are allotted with a budget equal to k * log n log m (i.e., the cost of the on-line algorithm of [START_REF] Alon | The online set cover problem[END_REF]) and we assume that the fine paid by algorithm GREEDY is also computed with respect to the algorithm of [START_REF] Alon | The online set cover problem[END_REF]), then a similar analysis as in the proof of Theorem 4 leads to the same result, i.e., that GREEDY remains asymptotically optimum.

Also, if the budget allotted is k * √ and one calls the on-line algorithm of [START_REF] Alon | The online set cover problem[END_REF], this latter algorithm is asymptotically optimum for budget saving.

Discussion

We have introduced several simple on-line models for set-covering and analyzed greedy rules for them. Many of these rules are strongly competitive since no on-line algorithm for the models that they treat can achieve better ratios than they do. One of the features of the models studied here is that they are very economic and thus suitable to solve very large instances. Indeed, their memory requirements are extremely reduced since the only information needed are the names of m sets. Note that this is not the case for the intensive computations implied by the very interesting model of [START_REF] Alon | The online set cover problem[END_REF].

Next, we have introduced and studied the maximum budget saving problem. Here, we have relaxed irrevocability in the solution construction by allowing the algorithm to delay its decisions modulo some fine to be paid. For such a model we have shown that the natural greedy off-line algorithm is asymptotically optimum.

A subject for further research is the extension of our models to deal with minimum-weight For this version work is in progress. Finally, let us note that the on-line models described in the paper can be extended to apply to a different but related problem, the minimum dominating set. Consistently with the model that we have adopted for the set-covering problem, our model for this latter problem is as follows. Given a graph G(V, E) with |V | = n, assume that its vertices switch on one-by-one. Any time a vertex σ i switches on, the names of its neighbors are announced.

Consider the following classical reduction from minimum dominating set to set-covering:

• the set S i ∈ S, corresponding to the vertex

The set-covering instance (S, C) so constructed, has |S| = |C| = n. Furthermore, it is easy to see that any set cover of size k in (S, C) corresponds to a dominating set of the same size in G and vice-versa. Remark also that the dominating set model just assumed on G is exactly, with respect to (S, C), the set-covering model dealt in the paper.


Camil Demetrescu
email: demetres@dis.uniroma1.it

Bruno Escoffier
email: escoffier@lamsade.dauphine.fr

Gabriel Moruz

Andrea Ribichini
email: ribichini@dis.uniroma1.it

Parallel Algorithms are Good for Streaming

come

Introduction

Data stream processing has gained increasing popularity in the last few years as an effective paradigm for processing massive data sets. Huge data streams arise in several modern applications, including database systems, IP traffic analysis, sensor networks, and transaction logs [START_REF] Gilbert | Quicksand: Quick summary and analysis of network data[END_REF][START_REF] Golab | Data stream management issues Ð a survey[END_REF][START_REF] Sullivan | Tribeca: A system for managing large databases of network traffic[END_REF]. Streaming can be an effective paradigm also in scenarios where the input data is not necessarily represented in the form of a data stream. Due to the high sequential access rates of modern disks, streaming algorithms can be effectively deployed for processing massive files on secondary storage [START_REF] Henzinger | External Memory algorithms[END_REF], providing new insights into the solution of several computational problems in external memory. In the classical read-only streaming model, algorithms are constrained to access the input data sequentially in one (or few) passes, using only a small amount of working memory, typically much smaller than the size of the input [START_REF] Henzinger | External Memory algorithms[END_REF][START_REF] Munro | Selection and sorting with limited storage[END_REF][START_REF] Muthukrishnan | Data streams: algorithms and applications[END_REF]. Usual parameters of the model are the working memory size s and the number of passes p that are performed over the data, which are usually functions of the input size. Among the problems that have been studied in this model under the restriction that p = O(1), we recall statistics and data sketching problems (see, e.g., [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF][START_REF] Feigenbaum | An approximate L 1 difference algorithm for massive data streams[END_REF][START_REF] Gilbert | Fast, small-space algorithms for approximate histogram maintenance[END_REF]), which can be typically approximated using polylogarithmic working space, and graph problems (see, e.g., [START_REF] Bar-Yossef | Reductions in streaming algorithms, with an application to counting triangles in graphs[END_REF][START_REF] Feigenbaum | On graph problems in a semi-streaming model[END_REF][START_REF] Feigenbaum | Graph distances in the streaming model: the value of space[END_REF][START_REF] Mcgregor | Finding matchings in the streaming model[END_REF]), most of which require a working space linear in the vertex set size.

Motivated by practical factors, such as the availability of large amounts of temporary storage at low cost, some authors have recently proposed less restrictive streaming models where algorithms can both read and write data streams. Among them, we mention the W-Stream model and the StrSort model [START_REF] Aggarwal | On the streaming model augmented with a sorting primitive[END_REF][START_REF] Ruhl | Efficient Algorithms for New Computational Models[END_REF]. In the W-Stream model, at each pass one input stream is read and one output stream is written; streams are pipelined in such a way that the output stream produced at pass i is given as input stream at pass i+1. Despite the use of intermediate streams, which allows it to achieve effective space-passes tradeoffs for fundamental graph problems, most classical lower bounds in read-only streaming hold also in this model [START_REF] Demetrescu | Trading off space for passes in graph streaming problems[END_REF]. The StrSort model is just W-Stream augmented with a sorting primitive that can be used to reorder each intermediate stream for free. The use of sorting provides a lot of power, making it possible to solve several graph problems with polylogarithmic space and passes [START_REF] Aggarwal | On the streaming model augmented with a sorting primitive[END_REF]. For a comprehensive survey of algorithmic techniques for processing data streams, we refer the interested reader to the extensive bibliographies in [START_REF] Babcock | Models and issues in data stream systems[END_REF][START_REF] Muthukrishnan | Data streams: algorithms and applications[END_REF].

It is well known that algorithmic ideas developed in the context of parallel computational models have inspired the design of efficient algorithms in other models. For instance, Chiang et al. [START_REF] Chiang | External-memory graph algorithms[END_REF] showed that efficient external memory algorithms for several problems can be derived from PRAM algorithms using a general simulation. Recently, Aggarwal et al. [START_REF] Aggarwal | On the streaming model augmented with a sorting primitive[END_REF] discussed how uniform linear width, poly-logarithmic depth circuits can be simulated efficiently in the StrSort model, providing a systematic way of constructing algorithms in this model for problems in NC that use a linear number of processors. Examples of problems in this class include undirected connectivity and maximal independent set. Parallel techniques seem to play a crucial role in the design of efficient algorithms in the W-Stream model as well. For instance, the single-source shortest paths algorithm described in [START_REF] Demetrescu | Trading off space for passes in graph streaming problems[END_REF] is inspired by a framework introduced by Ullman and Yannakakis [START_REF] Ullman | High-probability parallel transitive-closure algorithms[END_REF] for the parallel transitive closure problem. However, to the best of our knowledge no general techniques for simulating parallel algorithms in the W-Stream model have been addressed so far in the literature.

Our contributions. In this paper, we show how PRAM algorithms can be turned into near-optimal streaming algorithms for several classical combinatorial problems in the W-Stream model. As a first step, we show that any PRAM algorithm that runs in time T using N processors and memory M can be simulated in W-Stream using p = O((T • N • log M )/s) passes. This yields near-optimal trade-off upper bounds of the form p = O((n • polylog n)/s) in W-Stream for several problems on sequences and forests of size n. Relevant examples include sorting, list ranking, and Euler tour. For other problems, however, this simulation does not provide good upper bounds. One prominent example is given by graph problems, for which efficient PRAM algorithms typically require O(m + n) processors on graphs with n vertices and m edges. For those problems, our first simulation method would yield bounds of the form p = O((m • polylog n)/s), while p =Ω(n/s) almost-tight lower bounds in W-Stream are known for many of them.

To overcome this problem, we study an intermediate parallel model, which we call RPRAM, derived from the PRAM model by relaxing the assumption that a processor can only access a constant number of cells at each round. For some problems, this allows it to reduce substantially the number of processors while maintaining the same number of rounds. While this may be unrealistic in practice, we show that simulating RPRAM algorithms in W-Stream leads to near-optimal algorithms (up to polylogarithmic factors) for several fundamental problems, including sorting, minimum spanning tree, biconnected components, and maximal independent set. Algorithms obtained in this way may not always be optimal (although very close to being so): we prove this by showing that for some of the problems above there are better algorithms designed directly in W-Stream without using simulations.

Finally, we show that there exist problems for which the increased computational power of the RPRAM model cannot be exploited to reduce the number of processors required by a PRAM algorithm while maintaining the same time bounds, and thus cannot lead to better W-Stream algorithms: one example is deciding whether a directed graph contains a cycle of length two.

Simulating parallel algorithms in W-Stream

In this section we show general techniques for simulating parallel algorithms in the W-Stream model. As we will see in the next sections, our techniques yield near-optimal algorithms for many classical combinatorial problems in the W-Stream model. We first discuss how to simulate general CRCW PRAM algorithms.

Theorem 1 Let A be a PRAM algorithm that uses N processors and runs in time T using space M =poly(N ). Then A can be simulated in W-Stream in p = O((T •N •log M )/s) passes using s bits of working memory and intermediate streams of size O(M + N ).

Proof (Sketch). In the PRAM model, at each parallel round every processor can read O(1) memory cells, perform O(1) instructions to update its internal state, and possibly write O(1) memory cells. We assume that each memory address, cell value, and processor state can be represented using O(log M ) bits. A round of A can be simulated in W-Stream by performing O((N log M )/s) passes, where at each pass we simulate the execution of Θ(s/ log M ) processors using s bits of working memory. The content of the memory cells accessed by the algorithm and the state of each processor are maintained on the intermediate streams as items of the form (address, value) and (processor, state), respectively. The task of each processor can be simulated in a constant number of passes by first reading from the input stream its state and the content of O(1) memory cells, executing an instruction of the algorithm, and then writing to the output stream the new state and possibly the values of the O(1) output cells. Memory cells that remain unchanged are simply propagated through the intermediate streams by just copying them from the input stream to the output stream at each pass. ✷

There are many examples of problems that can be solved near-optimally in W-Stream using Theorem 1. For instance, list ranking can be solved in PRAM in O(log n) rounds and O(n/ log n) processors [START_REF] Anderson | A simple randomized parallel algorithm for list-ranking[END_REF], where n is the length of the list; by Theorem 1, this yields a W-Stream algorithm that runs in O((n log n)/s) passes. As another example, an Euler tour of a tree with n vertices can be found in parallel in O(1) rounds using n processors [START_REF] Jájá | An introduction to parallel algorithms[END_REF], which by Theorem 1 yields again a p = O((n log n)/s) bound in W-Stream. However, for other problems, the bounds that can be obtained in this way are far from optimal. For instance, efficient PRAM algorithms for graph problems typically require (m + n) processors, where n is the number of vertices, and m is the number of edges. For these problems, Theorem 1 yields bounds of the form p = O((m • polylog n)/s), while p =Ω(n/s) almost-tight lower bounds are typically known for many of them.

We now introduce a variant of the PRAM model, which would be completely unrealistic in a practical setting, but will be useful to derive efficient algorithms in W-Stream for problems where Theorem 1 does not yield good results.

Definition 1 An RPRAM (Relaxed PRAM) is an extended CRCW PRAM machine with N processors and memory size M where at each round a processor can execute O(M ) instructions, which:

• can read all the values stored in memory. Each value can only be read a constant number of times, and no assumptions can be made as to the order in which values are given to the processor;

• can write an arbitrary subset of the memory cells. The result of concurrent writes to the same cell in the same round is undefined. Writing can only be performed after all read operations have been done.

Similarly to a PRAM, each processor has a constant number of registers of size O(log M ) bits.

Notice that, while in a PRAM each processor can read/write only O(1) memory cells at each round, in an RPRAM this restriction is relaxed so that any number of cells can be accessed in the same parallel round. This jump in computational power allows it to reduce substantially the number of processors used by many classical PRAM algorithms while maintaining the same number of parallel rounds, or even reducing it. As shown below, parallel algorithms implemented in this more powerful model can be simulated in W-Stream within the same bounds of Theorem 1.

Theorem 2 Let A be an RPRAM algorithm that uses N processors and runs in time Proof (Sketch). The claim can be proven similarly to Theorem 1. The main difference is that a processor in the RPRAM model can read and write several memory cells at each round, executing many instructions while still using O(log M ) bits to maintain its internal state. Since the instructions of algorithm A performed by a processor during a round do not assume any particular order for reading the memory cells, reading memory values from the input stream can still be simulated in one pass. Since writing operations occur after all reads have been done, updating memory values can be performed in an additional pass by replacing cell values read from the input stream with the new values in the output stream. ✷

T using space M =p o l y ( N ). Then A can be simulated in W-Stream in p = O((T • N • log M )/s)
In the remainder of this paper, we show that parallel algorithms for several classical problems can be naturally implemented in the RPRAM model, yielding by Theorem 2 efficient algorithms in W-Stream.

Sorting

As a first simple application of the simulation techniques introduced in Section 2, we show how to derive efficient sorting algorithms in W-Stream.W efirst recall that n items can be sorted on a PRAM with O(n) processors in O(log n) parallel rounds [START_REF] Jájá | An introduction to parallel algorithms[END_REF]. By Theorem 1, this yields a W-Stream sorting algorithm that runs in p = O((n log 2 n)/s) passes. In RPRAM, however, sorting can be solved by O(n) processors in constant time as follows. Each processor is assigned to an input item; in one parallel round it scans the entire memory and counts the number of items smaller than and equal to the item the processor is assigned to. Let i and j be those numbers, respectively. Then each processor Cahiers du LAMSADE writes its own item into all the cells with indices in the range i +1through i +1+j, thus producing a sorted sequence. This yields the following theorem.

Theorem 3 Sorting n items in RPRAM can be done in O(1) parallel rounds using O(n) processors.

Using Theorem 2 and Theorem 3, we obtain a W-Stream sorting algorithm that takes p = O((n log n)/s) passes, thus matching the performance of the best known algorithm for sorting in a streaming setting [START_REF] Munro | Selection and sorting with limited storage[END_REF]. Since we can prove that sorting requires p = Ω(n/s) passes in the W-Stream model, this bound is essentially optimal.

Graph algorithms

In this section we discuss how to derive efficient W-Stream algorithms for several graph problems using the RPRAM simulation of Theorem 2. We notice that efficient PRAM graph algorithms typically require O(m + n) processors [START_REF] Blelloch | Parallel algorithms[END_REF] on graphs with n vertices and m edges. Simulating such algorithms in W-Stream using Theorem 1 would yield bounds of the form p = O((m • polylog n)/s), while p =Ω ( n/s) almost-tight lower bounds in W-Stream are known for many of them. Graph connectivity is one prominent example [START_REF] Demetrescu | Trading off space for passes in graph streaming problems[END_REF]. Notice that, assigning each vertex to a processor, RPRAM gives enough power for each vertex to scan its entire neighborhood in a single parallel round. Since many parallel graph algorithms can be implemented using repeated neighborhood scanning, in many cases this allows it to reduce the number of processors from O(m + n) to O(n) while maintaining the same running time. By Theorem 2, this yields improved bounds of the form p = O((n • polylog n)/s). We now show however that there are graph problems for which this is impossible.

Lemma 1 Testing whether a directed graph with m edges contains a cycle of length two requires p =Ω(m/s) passes in W-Stream.

Proof (Sketch). We prove the lower bound by showing a reduction from the bit vector disjointness two-party communication complexity problem. Alice has an m-bit vector A and Bob has an m-bit vector B; they wish to know whether A and B are disjoint, i.e. A • B>0. Let e(i)=( x i ,y i ) and let e r (i)=( y i ,x i ), where

x i = i div ⌈ √ m ⌉ and y i = i mod ⌈ √ m ⌉.
To make the reduction, Alice creates a stream containing an edge e(i) for each i such that A[i]=1and Bob creates a stream containing an edge e r (i) for each i such that B[i]=1. Let G be the directed graph induced by the union of the ≤ 2m edges in the streams created by Alice and Bob. Clearly, there is a cycle of length two in G if and only if A • B>0. Since solving bit vector disjointness requires transmitting Ω(m) bits [START_REF] Kushilevitz | Communication Complexity[END_REF], and the distributed execution of any streaming algorithm would require 6

Cahiers du LAMSADE the working memory image to be sent back and forth from Alice to Bob at each pass, it must be p • s =Ω(m). Hence, p =Ω(m/s). ✷ Lemma 1 implies that testing whether a directed graph has a cycle of length two requires Ω(m/(n log n)) rounds on an RPRAM with n processors. Notice that this problem can be easily solved in one round on a PRAM with O(m+n) processors, by just checking in parallel whether there is any edge (x, y) that also appears as (y, x) in the graph.

Connected components (CC)

A classical PRAM random-mating algorithm for computing the connected components of a graph with n vertices and m edges requires O(m + n) processors and O(log n) time with high probability [START_REF] Blelloch | Parallel algorithms[END_REF][START_REF] Reif | Optimal parallel algorithms for integer sorting and graph connectivity[END_REF]. We first recall how the algorithm works, and then we show that it can be implemented in RPRAM with just O(n) processors. By Theorem 2, this yields a near optimal algorithm in W-Stream.

Parallel algorithm. The algorithm is based on building a set of star subgraphs and contracting the stars. It iterates the following sequence of steps.

1. Each vertex is assigned the status of parent or child independently with probability 1/2; 2. For each child vertex u, determine if it is adjacent to a parent vertex. If so, choose one such a vertex to be the parent f (u) of u, and replace each edge (u, v) by (f (u),v) and each edge (v, u) by (u, f (v));

3. For each vertex having parent u, set the parent to f (u).

In this contraction phase, the probability that a vertex is assigned to a connected component, i.e. has a neighbor parent, is at least 1/4. It has been shown that with high probability the number of iterations is bounded by O(log n).

RPRAM implementation. Each iteration can be implemented in RPRAM in constant time using O(n) processors as follows. We attach a processor to each vertex. In a round we assign to each vertex the status of parent of child. In a second round each vertex scans its neighborhood to find a parent, if exists (in case of several parents, we can break ties arbitrarily). Updating the parents as in step three can also be done in one round. This yields the following bound.

Cahiers du LAMSADE

Theorem 4 CC can be solved in RPRAM using n processors in O(log n) rounds with high probability.

By Theorem 2, this yields the following bound in W-Stream.

Corollary 1 CC can be solved in W-Stream in O((n log 2 n)/s) passes with high probability.

By the p =Ω(n/s) lower bound for CC in W-Stream [START_REF] Demetrescu | Trading off space for passes in graph streaming problems[END_REF], this upper bound is optimal up to a polylogarithmic factor. We note however that CC can be solved deterministically in W-Stream in O((n log n)/s) passes [START_REF] Demetrescu | Trading off space for passes in graph streaming problems[END_REF].

Minimum spanning tree (MST)

As explained in [START_REF] Blelloch | Parallel algorithms[END_REF], the randomized CC algorithm given above can be extended to find a minimum spanning tree in a (connected) graph.

Parallel algorithm.

The algorithm is based on the property that given a subset V ′ of vertices, a minimum weight edge having one and only one endpoint in V ′ is in any MST. We modify the CC algorithm as follows. At the second step, each child vertex u determines the minimum weight incident edge (u, v).I fv is a parent vertex, then f (u)=v and flag the edge (u, v) as belonging to the spanning tree. If v is not a parent vertex, do nothing. This algorithm computes a MST and performs O(log n) iterations with high probability.

RPRAM implementation. Assuming that edge weights can be encoded using O(log n) bits, the modification does not affect significantly the number of rounds needed in RPRAM, since each iteration can still be performed in O(1) rounds.

Theorem 5 MST can be solved in RPRAM using n processors in O(log n) rounds with high probability.

By Theorem 2, we obtain the following bound in W-Stream.

Corollary 2 MST can be solved in

W-Stream in O((n log 2 n)/s) passes.
We now show that we can improve this bound by a log n factor with an algorithm designed directly in W-Stream.

W-Stream algorithm. We compute the MST by progressively adding edges as follows. We compute for each vertex the minimum weight edge incident to it. This set of edges E ′ is added to the MST. Then we compute the connected components induced by E ′ and contract the graph by considering each connected components as a single vertex. We repeat these steps until the graph contains a single vertex. More precisely, we consider at each iteration a contracted graph where the vertices are the connected components of the partial MST so far computed. Let G i =(V i ,E i ) be the graph before the i th iteration:

1. for each vertex u ∈ V i ,wefind a minimum weight edge (u, v) incident to u and add (u, v) to the MST. Let

E ′ i = {(u, v),u ∈ V i };
2. we run a CC algorithm on the graph (V i ,E ′ i ). The connected components obtained in this way are the vertices of V i+1 ; 3. we replace each edge (u, v) by (c(u),c(v)), where c(u) and c(v) represent the labels of the connected components previously computed.

We now analyze the number of passes required in W-Stream.

Let |V i | = n i .
The first and the third steps require O((n i log n)/s) passes each, since we can process in one pass O(s/ log n) vertices. As computing the connected components takes O((n i log n)/s) passes, the i th iteration requires O((n i log n)/s) passes. We note that at each iteration, we add an edge for every vertex in V i . Hence, the number of connected components is divided by at least two. Therefore the total number of passes performed is given by T (n)=T (n/2) + O((n log n)/s), which sums up to O((n log n)/s).

Theorem 6 MST can be computed in O((n log n)/s) passes in W-Stream.

By the p =Ω(n/s) lower bound for CC in W-Stream [START_REF] Demetrescu | Trading off space for passes in graph streaming problems[END_REF], this upper bound is optimal up to a logarithmic factor. To the best of our knowledge, no previous algorithm was known for MST in W-Stream.

Biconnected components (BCC)

Tarjan and Vishkin [START_REF] Tarjan | Finding biconnected components and computing tree functions in logarithmic parallel time[END_REF] give a PRAM algorithm that computes the biconnected components (BCC) of an undirected graph in O(log n) time using O(m+n) processors. We give an RPRAM implementation of their algorithm that can be simulated in W-Stream using O((n log 2 n)/s) passes. We also give a direct implementation that uses only O((n log n)/s) passes.

Cahiers du LAMSADE

Parallel algorithm. Given a graph G, the algorithm considers a graph G ′ such that the vertices in G ′ correspond to the edges in G and the connected components of G ′ correspond to the biconnected components of G. The algorithm starts from a rooted spanning tree T on G and builds a subgraph G ′′ of G ′ having as vertices all the edges of T . The edges of G ′′ are built in such a way that two vertices are in the same connected component of G ′′ if and only if the corresponding edges in G are in the same biconnected component. After computing the connected components of G ′′ the algorithm appends the remaining edges of G to their corresponding biconnected component. We now briefly sketch the five steps of the algorithm:

1. build a rooted spanning tree T of G and compute for each vertex its preorder and postorder numbers together with the number of descendants. Also, the vertices are labelled with their preorder numbers.

2. compute for each vertex u two values, low(u) and high(u), given as follows.

low(u)=m i n ( {u}∪{low(w)|p(w)=u}∪{w|(u, w) ∈ G \ T }) high(u)=m a x ( {u}∪{high(w)|p(w)=u}∪{w|(u, w) ∈ G \ T }),
where p(u) denotes the parent of vertex u. 4. compute the connected components of G ′′ .

5. add the remaining edges of G to their biconnected components. Each edge (v, w) ∈ G \ T , with v<w, is assigned to the biconnected component of (p(w),w).

RPRAM implementation. We give RPRAM descriptions for all the five steps of the algorithm, each of them using O(log n) time and O(n) processors. First, we compute a spanning tree for the graph using the RPRAM algorithm previously introduced. Rooting the tree and computing for each vertex the preorder and postorder numbers as well as the number of descendants can be done using list ranking and Euler tour [START_REF] Tarjan | Finding biconnected components and computing tree functions in logarithmic parallel time[END_REF], which take O(log n) time and O(n) processors in PRAM, thus in RPRAM. Since the second step takes O(log n) time using O(n) processors in PRAM [START_REF] Tarjan | Finding biconnected components and computing tree functions in logarithmic parallel time[END_REF], the same bounds hold for RPRAM. As for the third step, we implement it in RPRAM in constant time and O(n) processors by allowing every vertex to read its neighborhood. For computing the connected components of G ′′ in the fourth step, we use the RPRAM algorithm previously introduced that takes O(log n) time and O(n) processors. Finally, we implement the last step of the algorithm in RPRAM in O(1) time and O(n) processors by reading for all vertices v the whole neighborhood and assign the edges to the proper biconnected components.

Since all the steps of the algorithm can be implemented in RPRAM in O(log n) rounds and O(n) processors, we get the following result. We now show that we can improve this bound by a log n factor with an implementation designed directly in W-Stream.

W-Stream algorithm. We describe how to implement directly in W-Stream the steps of the parallel algorithm of Tarjan and Vishkin [START_REF] Tarjan | Finding biconnected components and computing tree functions in logarithmic parallel time[END_REF]. Notice that we have given constant time RPRAM descriptions for the third and the fifth step, thus by applying the simulation in Theorem 2 we obtain W-Stream algorithms that run in O((n log n)/s) passes. For computing the connected components in the fourth step, we can use the algorithm in [START_REF] Demetrescu | Trading off space for passes in graph streaming problems[END_REF] that requires O((n log n)/s) passes. Therefore, to achieve a global bound of O((n log n)/s) passes, we must give implementations that run in O((n log n)/s) passes for the first two steps. For the first step, we can compute a spanning tree within the bound of Theorem 6. Rooting the tree and computing the preorder and postorder numbers together with the number of descendants can be easily implemented in O((n log n)/s) passes using list ranking, Euler tour and sorting. As for the second step, we compute the low and high values by processing s/ log n vertices at each pass, according to the postorder numbers.

Theorem 8 BCC can be solved in

W-Stream in O((n log n)/s) passes.
By the p =Ω(n/s) lower bound for CC in W-Stream [START_REF] Demetrescu | Trading off space for passes in graph streaming problems[END_REF], this upper bound is optimal up to a logarithmic factor. To the best of our knowledge, no previous algorithm was known for BCC in W-Stream.

Maximal independent set (MIS)

We give an efficient RPRAM algorithm for the maximal independent set problem (MIS), based on the PRAM algorithm proposed by Luby [START_REF] Luby | A simple parallel algorithm for the maximal independent set problem[END_REF]. Through the simulation in Theorem 2, this leads to an efficient W-Stream implementation.

Cahiers du LAMSADE

Parallel algorithm. A maximal independent set S of a graph G can be built incrementally through a series of iterations, as follows. At each iteration, in the first step, a random subset I of the vertices in G is determined, by including each vertex with probability 1/(2 • deg(v)). Then, in the second step, for each edge (u, v) of G such that u, v ∈ I, the vertex with the smallest degree is removed from I. Finally, in the third step, the vertices in I are added to S, and then both the vertices in I and their neighbors are removed from G. The above steps are repeated until G gets empty.

RPRAM implementation. The first step of each iteration can clearly be implemented in constant time by an RPRAM with O(n) processors, since each vertex can compute its own degree in one parallel round. The second step also can be implemented in constant time, by having each vertex in I scan its neighborhood, and remove itself if it encounters a neighbor also in I and with a larger degree. Finally, the third step can be implemented in constant time as well, since each vertex not in I, in just one parallel round, can scan its neighborhood and remove itself from G if one of its neighbors is in I. We now show that the bound of Corollary 4 is optimal up to a polylogarithmic factor. Theorem 10 MIS requires Ω(n/s) passes in W-Stream.

Proof (Sketch). The proof is based on a reduction from the bit vector disjointness communication complexity problem. Alice and Bob have each a vector of size n. They build a graph on 4n vertices v j i , where i =1,

3 .

 3 add edges to G ′′ according to the following two rules. For all (w, v) ∈ G \ T with v + desc(v) ≤ w, add ((p(v),v), (p(w),w)) to G ′′ and for all (v, w) ∈ T with p(w)=v and v =1 , add ((p(v),v), (v, w)) to G ′′ if low(w) <vor high(w) ≥ v + desc(v), where desc(v) denotes the number of descendants of vertex v.

Theorem 7

 7 BCC can be solved in RPRAM using O(n) processors in O(log n) rounds. By Theorem 2, this yields the following bound in W-Stream. Corollary 3 BCC can be solved in W-Stream in O((n log 2 n)/s) passes.

Theorem 9

 9 MIS can be solved in RPRAM using O(n) processors in O(log n) rounds with high probability. By Theorem 2, this yields the following bound in W-Stream. Corollary 4 MIS can be solved in W-Stream in O((n log 2 n)/s) passes with high probability.

  ••• ,nand j =1, ••• , 4.I fA i =0, then Alice adds edges (v 1 i ,v 2 i ) and (v 3 i ,v 4 i ), whereas if B i =0, then Bob adds edges (v 1 i ,v 3 i ) and (v 2 i ,v 4 i ). The size of any MIS is 2n if A • B =0and strictly greater otherwise. ✷To the best of our knowledge, no previous algorithm was known for MIS in W-Stream.It remains an open question whether one can solve this problem more efficiently in this model.

Cahiers du LAMSADE

 [START_REF] Aggarwal | On the streaming model augmented with a sorting primitive[END_REF]Work supported in part the by the Danish National Research Foundation (BRICS, Basic Research in Computer Science, www.brics.dk), by the Sixth Framework Programme of the EU under contract number 001907 ("DELIS: Dynamically Evolving, Large Scale Information Systems"), and by the Italian MIUR Project ALGO-NEXT "Algorithms for the Next Generation Internet and Web: Methodologies, Design and Experiments".