Pinyan Lu

Changyuan Yu

AN IMPROVED RANDOMIZED TRUTHFUL MECHANISM FOR SCHEDULING UNRELATED MACHINES

Keywords:

We study the scheduling problem on unrelated machines in the mechanism design setting. This problem was proposed and studied in the seminal paper of Nisan and Ronen [NR99], where they gave a 1.75-approximation randomized truthful mechanism for the case of two machines. We improve this result by a 1.6737-approximation randomized truthful mechanism. We also generalize our result to a 0.8368m-approximation mechanism for task scheduling with m machines, which improve the previous best upper bound of 0.875m[MS07].

Introduction

Mechanism design has become an active area of research both in Computer Science and Game Theory. In the mechanism design setting, players are selfish and wish to maximize their own utilities. To deal with the selfishness of the players, a mechanism should both satisfy some game-theoretical requirements such as truthfulness and some computational properties such as good approximation ratio. The study of their algorithmic aspect was initiated by Nisan and Ronen in their seminal paper "Algorithmic Mechanism Design" [START_REF] Nisan | Algorithmic mechanism design[END_REF]. The focus of that paper was on the scheduling problem on unrelated machines, for which the standard mechanism design tools ( VCG mechanisms [Clarke71, Groves1973, Vickrey61])do not suffice. They proved that no deterministic mechanism can have an approximation ratio better than 2 for this problem. This bound is tight for the case of two machines. However if we allow randomized mechanisms, this bound can be beaten. In particular they gave a 1.75-approximation randomized truthful mechanism for the case of two machines. Since then, many researchers have studied the scheduling problem on unrelated machines in mechanism design setting [JP99, Sourd01, SS02, SX02, GMW07, CKV07, CKK07, MS07]. However their mechanism remains the best to the best of our knowledge. In a recent paper [START_REF] Mu'alem | Setting lower bounds on truthfulness[END_REF], Mu'alem and Schapira proved a lower bound of 1.5 for this setting. So to explore the exact bound between 1.5 and 1.75 is an interesting open problem in this area. In this paper, we improve the upper bound from 1.75 to 1.6737. Formally we give a 1.6737-approximation randomized truthful mechanism for task scheduling with two machines. Using similar techniques of [START_REF] Mu'alem | Setting lower bounds on truthfulness[END_REF], we also generalize our result to a 0.8368m-approximation mechanism for task scheduling with m machines.

Let us describe the problem more carefully. There are m machines and n tasks, and each machine is controlled by an agent. We use t i j to denote the running time of task j on machine i, which is also called the type value of the agent(machine) i on task j. The objective is to minimize the completion time of the last assignment (the makespan). Unlike in the classical optimization problem, the scheduling designer does not know t i j . Each selfish agent i holds his/her own type values (the t i j s). In order to motivate the agents to report their true value t i j s, the mechanism needs to pay the agents. So a mechanism consists of an allocation algorithm and a payment algorithm. A mechanism is called truthful when telling one's true value is among the optimal strategies for each agent, no matter how other agents behave. Here the utility of each agent is the payment he/she gets minus the load of tasks allocated to his/her machine. When randomness is involved, there are two versions of truthfulness: in the stronger version, i.e. universally truthfulness, the mechanism remains truthful even if the agents know the random bits; in the weaker version, i.e. truthfulness in expectation, an agent maximizes his/her expected utility by telling the true type value. Our mechanisms proposed in this paper are universally truthful. Now we can talk about the high level idea of the technical part. Here we only talk about the allocation algorithms, and the corresponding payment algorithms, which make the mechanism truthful, will be given later. First we describe Nisan and Ronen's mechanism [START_REF] Nisan | Algorithmic mechanism design[END_REF]. In their mechanism, each task is allocated independently. For a particular task j, if the two values t 1 j and t 2 j are relatively close to each other, say t 1 j /t 2 j ∈ [3/4, 4/3], then they allocate task j randomly to machine 1 or 2 with equal probability; if one is much higher then the other, say t 1 j /t 2 j > 4/3 or t 2 j /t 1 j > 4/3, the task j is allocated to the more efficient machine. The main idea of our mechanism is to partition the tasks into three categories rather than two. So we need two threshold values, say α, β, where 1 < β < α and a biased probability r , where 1/2 < r < 1. If the two values are relatively close to each other, say t 1 j /t 2 j ∈ [1/β, β], or one is much higher then the other, say t 1 j /t 2 j > α or t 2 j /t 1 j > α , we do the same things as Nisan and Ronen's mechanism. In the remaining case, one is significantly larger than the other, but however still does not dominate, say

t 1 j /t 2 j ∈ [β, α] or t 2 j /t 1 j ∈ [β, α].
In this case, we allocate the task j to the more efficient one with a higher probability r (r > 1/2) and the less efficient one with a lower probability 1r. The mechanism is quite simple, so it is very computationally efficient. Intuitively our mechanism will give better approximation ratios by choosing suitable parameters α, β and r. This is indeed true. We can prove an improved approximation ratio of 1.6737 by choosing α = 1.4844, β = 1.1854, r = 0.7932. However, the proof is quite involved. One reason is that the situation for the new case (middle case) is more complicated than the original two. The main reason is that their approach becomes infeasible in the analysis of our mechanism. The proof in Nisan and Ronen's paper is basically case by case, but unfortunately the number of subcases increases double exponentially with the number of task types. So we introduce some substantial new proof techniques to overcome this. We also think this techniques may further improve the upper bound.

Related Work

Scheduling on unrelated machines is one of the most fundamental scheduling Problems. For this NP-hard optimization problem, there is a polynomial time algorithm with approximation ratio of 2 [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF]. Especially if the number of machines is bounded by some constant, Angel, Bampis and Kononov gave an FPTAS [START_REF] Angel | A FPTAS for Approximating the Unrelated Parallel Machines Scheduling Problem with Costs[END_REF]. However there is no corresponding payment strategy to make either of the above allocation algorithms truthful.

The study of this problem in the mechanism design setting is initiated by Nisan and Ronen. In their paper [START_REF] Nisan | Algorithmic mechanism design[END_REF], they gave a 1.75-approximation randomized truthful mechanism for two machines. This result was generalized by Mu'alem and Schapira to a 0.875mapproximation randomized mechanism for m machines [START_REF] Mu'alem | Setting lower bounds on truthfulness[END_REF]. We improved the two upper bounds to 1.6737 and 0.8368m respectively.

For the lower bound side, Nisan and Ronen gave a lower bound of 2 for deterministic version. This bound was improved by Christodoulou, Koutsoupias and Vidali to 1 + √ 2 for 3 or more machines [START_REF] Christodoulou | A lower bound for scheduling mechanisms[END_REF]. For the randomized version, Mu'alem and Schapira gave a lower bound of 2 -1/m [START_REF] Mu'alem | Setting lower bounds on truthfulness[END_REF]. This also holds for the weaker notion of truthfulness, i.e., truthfulness in expectation.

Lavi and Swarmy considered a restricted variant, where each task j only has two values of running time , and gave a 3-approximation randomized truthful mechanism [START_REF] Lavi | Truthful mechanism design for multi-dimensional scheduling via cyclemonotonicity[END_REF]. They first use the cycle monotonicity in designing mechanisms.

In [START_REF] Christodoulou | Mechanism Design for Fractional Scheduling on Unrelated Machines[END_REF], Christodoulou, Koutsoupias and Kovács considered the fractional version of this problem, in which each task can be split among the machines. For this version, they gave a lower bound of 2 -1/m and an upper bound of (m + 1)/2. We remark that these two bounds are closed for the case of two machines as in the integral deterministic version. So to explore the exact bound for the randomized version seems very interesting and desirable. We believe that our work in this paper is an important step toward this objective.

Problem and Definitions

In this section we review some definitions and results on mechanism design and scheduling problem. More details can be found in [START_REF] Nisan | Algorithmic mechanism design[END_REF].

In a mechanism design problem, there are usually some resources to distribute among n agents. Every agent i has a type value t i , which denotes his/her preference on the resources. Let t = (t i ) i∈[m] denote the vector of all agents' type values and t -i denote the vector of all agents' type vectors except agent i's. Receiving all the type values t from agents, the mechanism will produce an output o(t) = (x(t), p(t)). Here x(t) specifies the allocation of the resources and is produced by an allocation algorithm. p(t) specifies the payment to agents and is produced by an payment algorithm. Every agent i has a valuation v i (x, t i ), which describe his/her preference on the output allocation. The agent i's objective is maximizing his/her utility function u i , where u i = v i + p i , and p i is the payment obtained from the mechanism. The mechanism's objective is to maximize an objective function g(o, t). Formally, we have the following definitions.

Definition 2.1. A mechanism is a pair of Algorithms M = (X, P ).

• Allocation Algorithm X: Its input is m agents' type vectors, t 1 , t 2 , • • • , t m , which are reported by the agents. and its output is

x = (x 1 , • • • , x m )
, where x i = (x i j ) j∈[n] ∈ {0, 1} n are allocation vector of agent i.

• Payment Algorithm P : It outputs a payment vector p = (p 1 , • • • , p m ), which depends both on agents' type vectors and allocation vectors produced by allocation algorithm.

A mechanism is deterministic if both the allocation algorithm and payment algorithm are deterministic. When at least one of them uses random bits, it is called a randomized mechanism.

In order to increase utility, an agent may lie when reporting his/her type values. But for some mechanisms, no agent can increase his/her utility by lying. This nice property of a mechanism is called truthfulness. We give the formal definitions of truthfulness.

Definition 2.2. A deterministic mechanism is truthful iff for every agent, reporting his/her true type values is among the best strategies to maximize his/her utility, no matter how other agents acts. A randomized mechanism is truthful in expectation iff no agent can increase his/her expected utility by lying. A randomized mechanism is universally truthful iff it remains truthful even if the agents know the random bits.

From now on, we will only focus on truthful mechanisms. The most important positive result in mechanism design is generalized Vickrey-Clarke-Groves(VCG) mechanism [Vickrey61, Groves1973, Clarke71]. Many known truthful mechanisms are all in VCG family. The mechanisms of VCG family usually apply to mechanism design problem in which the objective function is the (weighted) sum of all agents' valuations. To be formal, we have Definition 2.3. [NR99] A mechanism M = (X, P ) belongs to weighted VCG family if there are real numbers(weights) β 1 , • • • , β n > 0, such that:

(1) the problem's objective function satisfies g(o, t) = i β i v i (t i , o).

(2) o(t) ∈ argmax o (g(o, t).

(3) p i (t) = 1

β i i ′ =i β i ′ v i ′ (t i ′ , o(t)) + h i (t -i )
, where h i () is an arbitrary function of t -i . Theorem 2.4. ([Roberts79]) A weighted VCG mechanism is truthful. Now we specify these mechanism notions in the problem of scheduling unrelated machines. Assume there are n tasks to be allocated to m machines, each of which is controlled by an agent. Each agent i's type value is

t i = (t i j ) j∈[n]
, where t i j denotes the time to perform task j on machine i.

We use a binary array

x i = (x i j ) j∈[n]
to specify the allocation of tasks to machine i. x i j is 1 if task j is allocated to machine i and otherwise 0. Let x = (x i ) i∈[m] denote the allocation of all the tasks. For an allocation x, agent i's valuation is

v i = -x i • t i , where x i • t i = n j=1 x i j t i j .
Definition 2.5. Given any allocation x of the tasks, the longest running time of the machines is called the makespan of the allocation. Formally, makespan(

x) = max i∈[m] x i • t i .
The objective of the mechanism is to minimize the (expected) makespan of the allocation. This is not the (weighted) sum of all agents' valuations. So we can not apply VCG mechanism here. However, we remark that if there is only one task, the makespan can be viewed as the sum of all agents' valuations. We will use this observation in our analysis.

From [START_REF] Nisan | Algorithmic mechanism design[END_REF] and [START_REF] Mu'alem | Setting lower bounds on truthfulness[END_REF], we know that there is no optimal truthful mechanism for this problem, even if we allow super-polynomial running time and randomness. So we will try to find a truthful mechanism with good approximation ratio. Definition 2.6. Let t M (t) be the (expected) makespan of the mechanism M on instances t and t opt (t) be the optimal makespan of instance t. We say mechanism M has approximation ratio c iff for any instance t, t M (t)/t opt (t) ≤ c.

Our Mechanism and the Analysis

In this section, we give a truthful scheduling mechanism for 2 machines case, and show that its approximation ratio is 1.6737. Then we generalize our result to the m machines case as in [START_REF] Mu'alem | Setting lower bounds on truthfulness[END_REF] and obtain a 0.8368m-approximation randomized truthful mechanism.

Generalized Randomly Biased Mechanism

Parameters: Real numbers α > β ≥ 1 > r ≥ 1 2 . (Here we choose α = 1.4844, β = 1.1854, r = 0.7932.) Input: The reported type vectors t = (t 1 , t 2 ). Output: A randomized allocation x = (x 1 , x 2 ), and a payment p = (p 1 , p 2 ). Allocation and Payment algorithm:

x 1 j ← 0, x 2 j ← 0, j = 1, 2 • • • , n; p 1 ← 0; p 2 ← 0. For each task j = 1, 2 • • • , n do s j ←          α,
with probability 1r, β, with probability r -1/2, 1/β, with probability r -1/2, 1/α, with probability 1r. if t 1 j < s j t 2 j , x 1 j = 1, p 1 ← p 1 + s j t 2 j ; else

x 2 j = 1, p 2 ← p 2 + s -1 j t 1 j . Theorem 3.1. The Generalized Randomly Biased Mechanism (GBM for short) is universally truthful and can achieve a 1.6737-approximation solution for task scheduling with two machines.

We will prove this theorem in the following two subsections. In 3.2, we will prove that our mechanism is universally truthful. Then we analyze its approximation ratio in 3.3

Truthfulness

Lemma 3.2. The Generalized Randomly Biased Mechanism is universally truthful.

Proof. To prove that the GBM is universally truthful, we only need to prove that it is truthful when the random sequence s j is fixed. Since the utility of an agent equals the sum of the utilities obtained from each task and our mechanism is task-independent, we only need consider the case of one task. In this case, say s j is fixed and there is only one task j, the mechanism is exactly the VCG mechanism with weight (1, s j ). Since a weighted VCG is truthful, the GBM mechanism is universally truthful.

Estimation of the Approximation Ratio

If this subsection, we will estimate the approximation ratio of our GBM mechanism. Since we already proved that GBM is universally truthful in 3.2, we only need to focus on the allocation algorithms of GBM. So we can restate the allocation algorithms for GBM in an equivalent but more understandable way. Intuitively we should assign one task with larger probability to the machine which has smaller type value(running time) on it. The idea of our mechanism is to partition all the tasks into several types according to the ratio of two agents' type values. For different types of tasks, we use different biased probabilities to allocate them. To be formal, we have the following definition. Definition 3.3. For a task j, we call it an h-task iff

t i j t 3-i j > α for some i ∈ {1, 2}; we called it an m-task iff β < t i j t 3-i j ≤ α for some i ∈ {1, 2}; we call it an l-task if t i j t 3-i j ≤ β for any i ∈ {1, 2}.
Then, we have the following claim.

Claim 3.4. The GBM mechanism allocates the tasks in the same way as the following allocating algorithm does.

• For h-task, we allocate it to the machine with lower type value.

• For m-task, we allocate it to the more efficient machine with probability r and to the less efficient machine with probability 1r. • For l-task, we allocate it to two machines with equal probabilities.

Proof. For each task j, we consider the probability that it is allocated to machine 1 in GBM.

According to the ratio of t 1 j t 2 j , we have the following 5 cases:

• Case 1: t 1 j ≥ αt 2 j , then P r(x 1 j = 1) = 0 • Case 2: β ≤ t 1 j < αt 2 j , then P r(x 1 j = 1) = 1 -r • Case 3: β -1 ≤ t 1 j < βt 2 j , then P r(x 1 j = 1) = (1 -r) + (r -1 2 ) = 1 2 • Case 4: α -1 ≤ t 1 j < β -1 t 2 j , then P r(x 1 j = 1) = (1 -r) + (r -1 2 ) + (r -1 2 ) = r • Case 5: t 2 j < α -1 t 2 j , then P r(x 1 j = 1) = (1 -r) + (r -1 2 ) + (r -1 2 ) + (1 -r) = 1
The probabilities that task j is assigned to machine 1 by two algorithms are always the same, so the lemma is true.

Remark 3.5. This claim only says that the (distribution of) allocation produced by the two methods are the same. However if we use this allocation algorithm stated in the claim, we can only make the mechanism truthful in expectation.

As in [START_REF] Nisan | Algorithmic mechanism design[END_REF], we obtain the following crucial claim, which can help us cut the number of tasks. The proof of this claim is similar , and we put it in the Appendix.

Claim 3.6. To analyze the performance of the generalized randomized biased mechanism, we only need consider the following cases:

(1) For each h-task j, the ratio of the two machines' type value is arbitrarily close to α.

So we can assume it equals α. (2) If OP T allocates an l-task j to machine i, then t 3-i j /t i j = β. (3) If OP T allocates an m-task j to machine i which has smaller type value, then t 3-i j /t i j = α.

(4) If OP T allocates an m-task j to machine i which has bigger type value, then t 3-i j /t i j = β -1 . (5) One of the machines is more efficient than the other on all h-tasks. We assume it's machine 1. (6) There are at most 8 tasks A, B, C, D, E, F, G, H. In OP T , tasks A, C, E, G are allocated to machine 1, and the others to machine 2. Tasks A, B are h-tasks. Tasks C, D, E, F are m-tasks and tasks G, H are l-tasks.

From the above analysis, we know that we only need to consider the reduced case as described in Figure 1.

type task t 1 j t 2 j opt-alloc gbm-alloc(probability) h 1 A a αa 1 1 : 0 h 2 B b αb 2 1 : 0 m 1 1 C c αc 1 r : (1 -r) m 1 2 D d βd 2 r : (1 -r) m 2 1 E βe e 1 (1 -r) : r m 2 2 F αf f 2 (1 -r) : r l 1 G g βg 1 1 2 : 1 2 l 2 H βh h 2 1 2 : 1 2 Figure 1: The Reduced Case.
Now we can estimate the approximation ratio based on this reduced case.

Lemma 3.7. The allocation produced by GBM is a 1.6737-approximation solution for the task scheduling problem with two machines.

Proof. Let t opt be the make-span of an optimal solution and let t gbm be the expected makespan of allocations produced by GBM. We want to show that t gbm ≤ 1.6737t opt .

From the allocation of the optimal solution, we have that

t opt = max{a + c + βe + g, αb + βd + f + h}.
Now we will estimate the expected makespan of our mechanism t gbm . First we introduce some notation which will be used in the following analysis. We will treat the same name X (X = A, B, • • • , H) as a random variable, which denotes the assignment of the task X. For example, C = 2 means that our mechanism assigns the task C to the second machine. Then the last column in Figure 1 can also be viewed as the distribution of the random variable X (X = A, B, • • • , H). For example P r(C = 1) = r and P r(C = 2) = 1r. Since our mechanism assigns each task independently, the random variables are also independent of each other. More precisely, for any X, Y ∈ {A, B, • • • , H}, i, j ∈ {1, 2} and X = Y , we have

P r(X = i, Y = j) = P r(X = i)P r(Y = j).
We use a random variable M to denote the machine finishing last. More precisely, M = 1 means the completion time of the first machine is not earlier than the second machine, otherwise we have M = 2. Now we compute the contribution of each task to t gbm . Let the j-th task be X. Then its contribution to t gbm contains two parts. First part is from t 1 j . t 1 j contributes to t gbm iff our mechanism assigns task X to 1 (e.t. X = 1) and the machine 1 finishes later (e.t. M = 1). The situation for t 2 j is similar. To sum up, the contribution of the j-th task X to t gbm is P r(M = 1, X = 1)t 1 j + P r(M = 2, X = 2)t 2 j . For example, the contribution of task C to t gbm is

P r(M = 1, C = 1)c + αP r(M = 2, C = 2)c = (P r(M = 1, C = 1) + αP r(M = 2, C = 2))c.
Similarly, we can compute the contribution of each task to t gbm easily. To simplify the notation, we use

C x (x = a, b, • • • , h) to denote the coefficient of x in t gbm . So we have t gbm = C a a + C b b + C c c + C d d + C e e + C f f + C g g + C h h.
where

C a = P r(M = 1), C b = P r(M = 1), C c = P r(M = 1, C = 1) + αP r(M = 2, C = 2), C d = P r(M = 1, D = 1) + βP r(M = 2, D = 2), C e = βP r(M = 1, E = 1) + P r(M = 2, E = 2), C f = αP r(M = 1, F = 1) + P r(M = 2, F = 2), C g = P r(M = 1, G = 1) + βP r(M = 2, G = 2), C h = βP r(M = 1, H = 1) + P r(M = 2, H = 2). Since t gbm = C a a + C b b + C c c + C d d + C e e + C f f + C g g + C h h = (C a a + C c c + C e β βe + C g g) + ( C b α αb + C d β βd + C f f + C h h) ≤ max(C a , C c , C e β , C g )(a + c + βe + g) + max( C b α , C d β , C f , C h )(αb + βd + f + h) ≤ max(C a , C c , C e β , C g )t opt + max( C b α , C d β , C f , C h )t opt
So the performance of our mechanism is bounded by

max(C a , C c , C e β , C g ) + max( C b α , C d β , C f , C h ).
We will give bound for every possible sum between

{C a , C c , Ce β , C g } and { C b α , C d β , C f , C h }. First C a + C b α = P r(M = 1) + P r(M = 1) α ≤ 1 + 1 α . So C a + C b α is bounded by 1 + 1 α .
Later we will choose suitable parameter α so that this value is not too big.

Now we analyze a more complicated case, say C c + C f . Substituting C c and C f , we have

C c +C f = P r(M = 1, C = 1)+αP r(M = 2, C = 2)+αP r(M = 1, F = 1)+P r(M = 2, F = 2).
Here we use P ijk to denote the joint distribution of three random variables M, C, F (e.t. P ijk = P r(M = i, C = j, F = k) ). Then we can rewrite the formula as following

(1 + α)P r(C = 2, F = 2) = r + α(1 -r) + (1 + α)r(1 -r) = 2r + α -r 2 -αr 2 .
Similarly we can bound the remaining 14 sums as follows. Some of proofs are slightly more complicated but all of them are along similar lines. We only list the bounds here, and the details are omitted here due to the space limitation.

(1)

C a + C d β ≤ 1 + r β . (2) C a + C f ≤ 1 + (1 -r)α. (3) C a + C h ≤ 1 + β 2 . (4) C c + C b α ≤ 1 + 1 α . (Here we use the assumption that α ≤ 1 + 1 α .) (5) C c + C d β ≤ r 2 β + 1 + r 2 + α -r + αr. (6) C c + C h ≤ 1 2 + 1 2 r + α -αr + 1 2 βr. (7) Ce β + C b α ≤ 1 + 1 α . (8) Ce β + C d β ≤ (1 -r) + 1 β r + (1 + 1 β )r(1 -r) ≤ C c + C f . (9) Ce β + C f ≤ r 2 β + 1 + r 2 + α -r + αr. (10) Ce β + C h ≤ 1 + r 2β + 1 2 β -1 2 r. (11) C g + C b α ≤ 1 + 1 α .
(Here we use the assumption that α

≤ 1 + 1 α .) (12) C g + C d β ≤ 1 + r 2β + 1 2 β -1 2 r. (13) C g + C f ≤ 1 2 + 1 2 r + α -αr + 1 2 βr. (14) C g + C h ≤ 3 4 + 3 4 β. To sum up, we have 9 different bounds: 1+ 1 α , 2r +α-r 2 -αr 2 , 1+ r β , 1+(1-r)α, 1+ β 2 , r 2 β + 1 + r 2 + α -r + αr, 1 2 + 1 2 r + α -αr + 1 2 βr, 1 + r 2β + 1 2 β -1 2 r, 3 4 + 3
4 β, and one assumption that α ≤ 1 + 1 α . We want to choose suitable parameter α, β, r such that the assumption is satisfied and the maximal bound is as small as possible. This can be easily done numerically by a mathematical tool such as Matlab. We can choose α = 1.4844, β = 1.1854, r = 0.7932. Substituting these values, we can verify that all the bounds are less than 1.6737. So we proved that our mechanism has an approximate ratio of 1.6737.

An Improved Mechanism for m Machines

As an application of our main result, we turn to the case of m machines. In [START_REF] Nisan | Algorithmic mechanism design[END_REF], Nisan and Ronen gave a truthful deterministic mechanism that achieves an m-approximation. Recently, Mu'alem and Schapira [START_REF] Mu'alem | Setting lower bounds on truthfulness[END_REF] generalized Nisan and Ronen's truthful randomized mechanism for 2 machines to the case of m machines. They partitioned the m machines into two sets of machines with equal size, S 1 and S 2 . Then they construct a new instance with only two machines, with type values t i j = min a∈S i t a j , i = 1, 2. Applying the mechanism for 2 machines case, They showed a universally truthful randomized mechanism that obtains an approximation of 0.875m. Using this idea and our improved result for two machines case, we can improve the ratio from 0.875m to 0.8368m. To be self contained, we give the formal description of the mechanism here. The proof is similar with [START_REF] Mu'alem | Setting lower bounds on truthfulness[END_REF] and omitted here.

' & $ % Parameters: real numbers α > β ≥ 1 > r ≥ 1 2 . Input: the reported type value vectors t = (t 1 , t 2 , • • • , t m ). Output: an randomized allocation x = (x 1 , x 2 , • • • , x m ) and a payment p = (p 1 , p 2 , • • • , p m ). Mechanism:
(1) For each machine i, let x i ← ∅; p i ← 0.

(2) Partition the set of machines into two sets S 1 , S 2 with equal size. If m is not even, we can add an extra machine with infinite type values on every task. (3) For each task j, Let t a = min i∈S

1 t i j , a = argmin i∈S 1 t i j , t a ′ = min i∈S 1 -{a} t i j . Let t b = min i∈S 2 t i j , b = argmin i∈S 1 t i j , t b ′ = min i∈S 1 -{a} t i j . ( 4
) Apply our mechanism GBM for two machines case to machine a and b on task j. Also the payment strategy need a little change. If a gets the task, and it will gain a payment p a j in GBM, then we pay it min{p a j , t a ′ j }. If b gets the task, and it will gain a payment p b j in GBM, then we pay it min{p b j , t b ′ j }. This change is in order to keep the mechanism truthful.

Theorem 3.8. m-GBM is an universally truthful randomized mechanism for the scheduling problem that obtains an approximation ratio of 0.8369m when choosing α = 1.4844, β = 1.1854, r = 0.7932.

Conclusions and Open Problems

This is the first improvement since Nisan and Ronen proposed the problem and the 1.75-mechanism. We believe it is possible to further improve the upper bound using our technics. A direct open problem is to close the gap between the lower bound of 1.5 and our new upper bound of 1.6737.

Another more important direction is to generalize the mechanisms for 2 machine to mechanisms for m machines in a more clever way. In the general case, the gap between the best lower bounds (constants) and the best upper bounds (Θ(m)) is huge both in deterministic and randomized versions. Any improvement in either direction is highly desirable. agent a has smaller type value. So there are 8 types of tasks. We will prove that any two task j 1 , j 2 of the same type can be combined into a single task j of the same type. Firstly, notice that j 1 , j 2 have the same ratio of the two agents' type values. so task j still has this ratio, hence the same type. Further more, they are all allocated by GBM with the same probability distribution.

In one direction, combining will leave t opt unchanged. Obviously, combining can only increase t opt because any allocation obtained for the new instance can be get for the old one. Also t opt can be achieved for the new instance since two tasks of the same type are allocated to the same agent.

In the other direction, combining can only increase t gbm . For the h-task case, t gbm is also unchanged because GBM always allocate the h-tasks to the more efficient agent.

For the m-task case, assume j 1 , j 2 are both m a b , a, b ∈ {1, 2}. Let Y denote an allocation of all the tasks except task j 1 , j 2 . Let t Y,j 1 ,j 2 (resp.t Y,j ) denote the expected make-span when j 1 , j 2 (resp. j) are (is) allocated by GBM and all other tasks are allocated according to Y . We have to show that t Y,j 1 ,j 2 ≤ t Y,j . Let T 1 , T 2 denote finishing time of two agents respectively when allocation is Y . If agent i finishes last regardless of how j 1 , j 2 are allocated, then t Y,j 1 ,j 2 = T i + r i (t i j 1 + t i j 2 ) = t Y,j Here r i denotes the probability that j 1 , j 2 and j are allocated to agent i. Otherwise, if agent i finishes last iff both j 1 , j 2 are allocated to it, then T 3-i ≤ T i + t i j 1 + t i j 2 t Y,j 1 ,j 2 = r 2 i (T i + t i j 1 + t i j 2 ) + r i (1r i )(T 3-i + t 3-i j 1 + T 3-i + t 3-i j 2 ) + (1r i ) 2 (T 3-i + t 3-i j 1 + t 3-i j 2 ) ≤ (r 2 i + r i (1r i ))(T i + t i j 1 + t i j 2 ) + ((1r i ) 2 + r i (1r i ))(T 3-i + t 3-i j 1 + t 3-i j 2 ) = r i (T i + t i j 1 + t i j 2 ) + (1r i )(T 3-i + t 3-i j 1 + t 3-i j 2 ) = t Y,j Finally assume that t i j 1 ≥ t i j 2 , i = 1, 2 and consider the last case where the agent to which j 1 is allocated finishes last. In this case t Y,j 1 ,j 2 = r 2 i (T i + t i j 1 + t i j 2 ) + r i (1r i )(T i + t i j 1 ) + r i (1r i )T 3-i + t 3-i j 1 ) + (1r i ) 2 (T 3-i + t 3-i j 1 + t 3-i j 2 ) ≤ (r 2 i + r i (1r i ))(T i + t i j 1 + t i j 2 ) + ((1r i ) 2 + r i (1r i ))(T 3-i + t 3-i j 1 + t 3-i j 2 ) = r i (T i + t i j 1 + t i j 2 ) + (1r i )(T 3-i + t 3-i j 1 + t 3-i j 2 ) = t Y,j

The l-task case is similar with m-task case, with r i = 1 2 .

P

  111 + P 112 + α(P 221 + P 222 ) + α(P 111 + P 121 ) + (P 212 + P 222 ). Then we recombine the terms as following (P 111 + P 112 + P 212 ) + α(P 111 + P 121 + P 221 ) + (1 + α)P 222 .The first term is bounded by P r(C = 1) (since P r(C = 1) = P 111 + P 112 + P 212 + P 211 ); similarly the second term is bounded by αP r(F = 1); the third term is bounded by (1 + α)P r(C = 2, F = 2). So we can bound C c + C f by P r(C = 1) + αP r(F = 1) +

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.

Supported by the National Natural Science Foundation of China Grant 60553001 and the National Basic Research Program of China Grant 2007CB807900, 2007CB807901. c P. Lu and C. Yu

Appendix

Proof of Claim 3.6

(1) For h-task j, assume t 1 j < t 2 j . We can decrease t 2 j to αt 1 j , then t gbm will not change since GBM always allocates task j to agent 1. But this may help OP T , so the approximation ratio can only be worse.

(2) Increasing t 3-i j to βt i j will not affect OP T but will increase t gbm . This is because the probability to allocate j does not change as long as it is still an l-task, and one type value is increased.

(3) It is similar with the above. We can keep increasing t 3-i j while j is still m-task. Here β ≤ t 3-i j /t i j ≤ α, so we can make it equal α. (4) Here β -1 ≥ t 3-i j /t i j ≥ α -1 , so we can increase t 3-i j until this ratio equals β -1 . (5) This is the same as in [START_REF] Nisan | Algorithmic mechanism design[END_REF]. We omit the proof here. (6) Let h a , l a , a ∈ {1, 2} denote an h-task or l-task respectively which is allocated to agent a in OP T . Let m a b , a, b ∈ {1, 2} denote an m-task allocated to agent b in OP T , on which


Ulrich Meyer
email: umeyer@ae.cs.uni-frankfurt.de

ON DYNAMIC BREADTH-FIRST SEARCH IN EXTERNAL-MEMORY

Keywords: Subject Classification: F.2.2 External Memory, Dynamic Graph Algorithms, BFS, Randomization

We provide the first non-trivial result on dynamic breadth-first search (BFS) in external-memory: For general sparse undirected graphs of initially n nodes and O(n) edges and monotone update sequences of either Θ(n) edge insertions or Θ(n) edge deletions, we prove an amortized high-probability bound of O(n/B 2/3 + sort(n) • log B) I/Os per update. In contrast, the currently best approach for static BFS on sparse undirected graphs requires Ω(n/B 1/2 + sort(n)) I/Os.

Introduction

Breadth first search (BFS) is a fundamental graph traversal strategy. It can also be viewed as computing single source shortest paths on unweighted graphs. It decomposes the input graph G = (V, E) of n nodes and m edges into at most n levels where level i comprises all nodes that can be reached from a designated source s via a path of i edges, but cannot be reached using less than i edges.

The objective of a dynamic graph algorithm is to efficiently process an online sequence of update and query operations; see [START_REF] Eppstein | Dynamic graph algorithms[END_REF][START_REF] Roditty | Dynamic and static algorithms for path problems in graphs[END_REF] for overviews of classic and recent results. In our case we consider BFS under a sequence of either Θ(n) edge insertions, but not deletions (incremental version) or Θ(n) edge deletions, but not insertions (decremental version). After each edge insertion/deletion the updated BFS level decomposition has to be output.

Computation models.

We consider the commonly accepted external-memory (EM) model of Aggarwal and Vitter [START_REF] Aggarwal | The input/output complexity of sorting and related problems[END_REF]. It assumes a two level memory hierarchy with faster internal memory having a capacity to store M vertices/edges. In an I/O operation, one block of data, which can store B vertices/edges, is transferred between disk and internal memory. The measure of performance of an algorithm is the number of I/Os it performs. The number of I/Os needed to read N contiguous items from disk is scan(N ) = Θ(N/B). The number of I/Os required to sort N items is sort(N ) = Θ((N/B) log M/B (N/B)). For all realistic values of N , B, and M , scan(N ) < sort(N ) ≪ N .

There has been a significant number of publications on external-memory graph algorithms; see [START_REF]Algorithms for Memory Hierarchies[END_REF][START_REF] Vitter | External memory algorithms and data structures: Dealing with massive data[END_REF] for recent overviews. However, we are not aware of any dynamic graph algorithm in the fully external-memory case (where |V | > M ).

Results.

We provide the first non-trivial result on dynamic BFS in external-memory. For general sparse undirected graphs of initially n nodes and O(n) edges and either Θ(n) edge insertions or Θ(n) edge deletions, we prove an amortized high-probability bound of O(n/B 2/3 +sort(n)• log B) I/Os per update. In contrast, the currently best bound for static BFS on sparse undirected graphs is O(n/B 1/2 + sort(n)) I/Os [START_REF] Mehlhorn | External-memory breadth-first search with sublinear I/O[END_REF].

Also note that for general sparse graphs and worst-case monotone sequences of Θ(n) updates in internal-memory there is asymptotically no better solution than performing Θ(n) runs of the linear-time static BFS algorithm, even if after each update we are just required to report the changes in the BFS tree (see Fig. 1 for an example). In case Ω(n/B 1/2 + sort(n)) I/Os should prove to be a lower bound for static BFS in external-memory, then our result yields an interesting differentiator between static vs. dynamic BFS in internal and external memory. Figure 1: Example for a graph class where each update requires Ω(n) changes in the BFS tree: inserting new (dashed) edges alternatingly shortcut the distances from s to X and s to Y. As a result, in the updated BFS tree the parents of all vertices in Z keep on changing between X and Y.

X s

Organization of the paper.

In Section 2 we will review known BFS algorithms for static undirected graphs. Then we consider traditional and new external-memory methods for graph clustering (Section 3). Subsequently, in Section 4 we provide the new algorithm and analyze it in Section 5. Final remarks concerning extensions and open problems are given in Sections 6 and 7, respectively.

Review of Static BFS Algorithms

Internal-Memory. BFS is well-understood in the RAM model. There exists a simple linear time algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF] (hereafter referred as IM BFS) for the BFS traversal in a graph. IM BFS keeps a set of appropriate candidate nodes for the next vertex to be visited in a FIFO queue Q. Furthermore, in order to find out the unvisited neighbors of a node from its adjacency list, it marks the nodes as either visited or unvisited.

Unfortunately, as the storage requirements of the graph starts approaching the size of the internal memory, the running time of this algorithm deviates significantly from the predicted O(n + m) asymptotic performance of the RAM model: checking whether edges lead to already visited nodes altogether needs Θ(m) I/Os in the worst case; unstructured indexed access to adjacency lists may add another Θ(n + m/B) I/Os. EM-BFS for dense undirected graphs. The algorithm by Munagala and Ranade [START_REF] Munagala | I/O-complexity of graph algorithms[END_REF] (referred as MR BFS) ignores the second problem but addresses the first by exploiting the fact that the neighbors of a node in BFS level t -1 are all in BFS levels t -2, t -1 or t. Let L(t) denote the set of nodes in BFS level t, and let A(t) be the multi-set of neighbors of nodes in L(t -1). Given L(t -1) and L(t -2), MR BFS builds L(t) as follows: Firstly, A(t) is created by |L(t -1)| random accesses to get hold of the adjacency lists of all nodes in L(t-1). Thereafter, duplicates are removed from A(t) to get a sorted set A ′ (t). This is done by sorting A(t) according to node indices, followed by a scan and compaction phase. The set L(t) := A ′ (t) \ {L(t -1) ∪ L(t -2)} is computed by scanning "in parallel" the sorted sets of A ′ (t), L(t -1), and L(t -2) to filter out the nodes already present in L(t -1) or L(t -2). The resulting worst-case

I/O-bound is O ( t L(t) + t sort(A(t))) = O (n + sort(n + m)).
The algorithm outputs a BFS-level decomposition of the vertices, which can be easily transformed into a BFS tree using O(sort(n + m)) I/Os [START_REF] Buchsbaum | On external memory graph traversal[END_REF].

EM-BFS for sparse undirected graphs. Mehlhorn and Meyer suggested another approach [START_REF] Mehlhorn | External-memory breadth-first search with sublinear I/O[END_REF] (MM BFS) which involves a preprocessing phase to restructure the adjacency lists of the graph representation. It groups the vertices of the input graph into disjoint clusters of small diameter in G and stores the adjacency lists of the nodes in a cluster contiguously on the disk. Thereafter, an appropriately modified version of MR BFS is run. MM BFS exploits the fact that whenever the first node of a cluster is visited then the remaining nodes of this cluster will be reached soon after. By spending only one random access (and possibly, some sequential accesses depending on cluster size) to load the whole cluster and then keeping the cluster data in some efficiently accessible data structure (pool) until it is all processed, on sparse graphs the total amount of I/Os can be reduced by a factor of up to √ B: the neighboring nodes of a BFS level can be computed simply by scanning the pool and not the whole graph. Though some edges may be scanned more often in the pool, unstructured I/Os to fetch adjacency lists is considerably reduced, thereby reducing the total number of I/Os.

Preprocessing

Traditional preprocessing within MM BFS.

Mehlhorn and Meyer [START_REF] Mehlhorn | External-memory breadth-first search with sublinear I/O[END_REF] proposed the algorithms MM BFS R and MM BFS D, out of which the first is randomized and the second is deterministic. In MM BFS R, the partitioning is generated "in parallel rounds": after choosing master nodes independently and uniformly at random, in each round, each master node tries to capture all unvisited neighbors of its current sub-graph into its partition, with ties being resolved arbitrarily.

A similar kind of randomized preprocessing is also applied in parallel [START_REF] Ullman | High-probability parallel transitive closure algorithms[END_REF] and streaming [START_REF] Demetrescu | Trading off space for passes in graph streaming problems[END_REF] settings. There, however, a dense compressed graph among the master nodes is produced, causing rather high parallel work or large total streaming volume, respectively.

The MM BFS D variant first builds a spanning tree T s for the connected component of G that contains the source node. Arge et al. [START_REF] Arge | On external-memory MST, SSSP and multi-way planar graph separation[END_REF] show an upper bound of O((1 + log log (B • n/m)) • sort(n + m)) I/Os for computing such a spanning tree. Each undirected edge of T s is then replaced by two oppositely directed edges. Note that a bi-directed tree always has at least one Euler tour. In order to construct the Euler tour around this bi-directed tree, each node chooses a cyclic order [START_REF] Atallah | Finding Euler tours in parallel[END_REF] of its neighbors. The successor of an incoming edge is defined to be the outgoing edge to the next node in the cyclic order. The tour is then broken at the source node and the elements of the resulting list are then stored in consecutive order using an external memory list-ranking algorithm; Chiang et al. [START_REF] Chiang | External memory graph algorithms[END_REF] showed how to do this in sorting complexity. Thereafter, we chop the Euler tour into chunks of max{1, n•B n+m } nodes and remove duplicates such that each node only remains in the first chunk it originally occurs; again this requires a couple of sorting steps. The adjacency lists are then re-ordered based on the position of their corresponding nodes in the chopped duplicate-free Euler tour: all adjacency lists for nodes in the same chunks form a cluster and the distance in G between any two vertices whose adjacency-lists belong to the same cluster is bounded by max{1,

n•B n+m }.

Modified preprocessing for dynamic BFS.

The preprocessing methods for the static BFS in [START_REF] Mehlhorn | External-memory breadth-first search with sublinear I/O[END_REF] may produce very unbalanced clusters: for example, with MM BFS D using chunk size 1 < µ < O( √ B) there may be Ω(n/µ) clusters being in charge of only O(1) adjacency-lists each. For the dynamic version, however, we would like to argue that each random access to a cluster not visited so far provides us with Ω(µ) new adjacency-lists. Unfortunately, finding such a clustering I/Oefficiently seems to be quite hard. Therefore, we shall already be satisfied with an Euler tour based randomized construction ensuring that the expected number of adjacency-lists kept in all but one1 clusters is Ω(µ).

The preprocessing from MM BFS D is modified as follows: each vertex v in the spanning tree T s is assigned an independent binary random number r(v) with P[r(v) = 0] = P[r(v) = 1] = 1/2. When removing duplicates from the Euler tour, instead of storing v's adjacencylist in the cluster related to the chunk with the first occurrence of a vertex v, now we only stick to its first occurrence iff r(v) = 0 and otherwise (r(v) = 1) store v's adjacency-list in the cluster that corresponds to the last chunk of the Euler tour v appears in. For leaf nodes v, there is only one occurrence on the tour, hence the value of r(v) is irrelevant. Obviously, each adjacency-lists is stored only once. Furthermore, the modified procedure maintains all good properties of the standard preprocessing within MM BFS D like guaranteed bounded distances of O(µ) in G between the vertices belonging to the same cluster and O(n/µ) clusters overall. Lemma 3.1. For chunk size µ > 1 and each but the last chunk, the expected number of adjacency-lists kept is at least µ/8.

Proof. Let R = (v 1 , . . . , v µ ) be the sequence of vertices visited by an arbitrary chunk R of the Euler tour T , excluding the last chunk. Let a be the number of entries in R that represent first or last visits of inner-tree vertices from the spanning tree T s on T . These a entries account for an expected number of a/2 adjacency-lists actually stored and kept in R. Note that if for some vertex v ∈ T both its first and last visit happen within R, then v's adjacency-list is kept with probability one. Similarly, if there are any visits of leaf nodes from T s within R, then their adjacency-lists are kept for sure; let b denote the number of these leaf node entries in R. What remains are µ -a -b intermediate (neither first nor last) visits of vertices within R; they do not contribute any additional adjacency-lists.

We can bound µ -a -b using the observation that any intermediate visit of a tree node v on T is preceded by a last visit of a child v ′ of v and proceeded by a first visit of another child v ′′ of v. Thus, µ -a -b ≤ ⌈µ/2⌉, that is a + b ≥ ⌊µ/2⌋, which implies that the expected number of distinct adjacency-lists being kept for R is at least ⌊µ/2⌋/2 ≥ µ/8.

The Dynamic Incremental Algorithm

In this section we concentrate on the incremental version for sparse graphs with Θ(n) updates where each update inserts an edge. Thus, BFS levels can only decrease over time. Before we start, let us fix some notation: for i ≥ 1, G i = (V, E i ) is to denote the graph after the i-th update, G 0 is the initial graph. Let d i (v), i ≥ 0, stand for the BFS level of node v if it can be reached from the source node s in G i and n otherwise. Furthermore, for i ≥ 1, let ∆d i (v) = |d i-1 (v) -d i (v)|. The main ideas of our approach are as follows:

Checking Connectivity; Type A updates. In order to compute the BFS levels for G i , i ≥ 1, we first run an EM connected components algorithm (for example the one in [START_REF] Munagala | I/O-complexity of graph algorithms[END_REF] taking O(sort(n)•log B) I/Os) in order to check, whether the insertion of the i-th edge (u, v) enlarges the connected component C s of the source vertex s. If yes (let us call this a Type A update), then w.l.o.g. let u ∈ C s and let C v be the connected component that comprises v. The new edge (u, v) is then the only connection between the existing BFS-tree for s and C v . Therefore, we can simply run MR BFS on the subgraph G ′ defined by the vertices in C v with source v and add d i-1 (u) + 1 to all distances obtained. This takes O(n v + sort(n)) I/Os where n v denotes the number of vertices in C v .

If the i-th update does not merge C s with some other connected component but adds an edge within C s (Type B update) then we need to do something more fancy:

Dealing with small changes; Type B updates. Now for computing the BFS levels for G i , i ≥ 1, we pre-feed the adjacency-lists into a sorted pool H according to the BFS levels of their respective vertices in G i-1 using a certain advance α > 1, i.e., the adjacency list for v is added to H when creating BFS level max{0, d i-1 (v)-α} of G i . This can be done I/O-efficiently as follows. First we extract the adjacency-lists for vertices having BFS levels up to α in G i-1 and put them to H where they are kept sorted by node indices. From the remaining adjacency-lists we build a sequence S by sorting them according to BFS levels in G i-1 (primary criterion) and node indices (secondary criterion). For the construction of each new BFS level of G i we merge a subsequence of S accounting for one BFS level in G i-1 with H using simple scanning.

Therefore, if ∆d i (v) ≤ α for all v ∈ V then all adjacency-lists will be added to H in time and can be consumed from there without random I/O. Each adjacency-list is scanned at most once in S and at most α times in H. Thus, if α = o( √ B) this approach causes less I/O than MM BFS.

Dealing with larger changes. Unfortunately, in general, there may be vertices v with ∆d i (v) > α. Their adjacency-lists are not prefetched into H early enough and therefore have to be imported into H using random I/Os to whole clusters just like it is done in MM BFS. However, we apply the modified clustering procedure described in Section 3.2 on G i-1 , the graph without the i-th new edge (whose connectivity is the same as that of G i ) with chunk size α/4.

Note that this may result in Θ(n/α) cluster accesses, which would be prohibitive for small α. Therefore we restrict the number of random cluster accesses to α • n/B. If the dynamic algorithm does not succeed within these bounds then it increases α by a factor of two, computes a new clustering for G i-1 with larger chunk size and starts a new attempt by repeating the whole approach with the increased parameters. Note that we do not need to recompute the spanning tree for the for the second, third, . . . attempt.

At most O(log B) attempts per update. The j-th attempt, j ≥ 1, of the dynamic approach to produce the new BFS-level decomposition will apply an advance of α j := 32 • 2 j and recompute the modified clustering for G i-1 using chunk size µ j := 8 • 2 j . Note that there can be at most O(log √ B) = O(log B) failing attempts for each edge update since by then our approach allows sufficiently many random accesses to clusters so that all of them can be loaded explicitly resulting in an I/O-bound comparable to that of static MM BFS. In Section 5, however, we will argue that for most edge updates within a longer sequence, the advance value and the chunk size value for the succeeding attempt are bounded by O(B 1/3 ) implying significantly improved I/O performance.

Restricting waiting time in H. There is one more important detail to take care of: when adjacency-lists are brought into H via explicit cluster accesses (because of insufficient advance α j in the prefetching), these adjacency-lists will re-enter H once more later on during the (for these adjacency-lists by then useless) prefetching. Thus, in order to make sure that unnecessary adjacency-lists do not stay in H forever, each entry in H carries a time-stamp ensuring that superfluous adjacency-lists are evicted from H after at most α j = O(2 j ) BFS levels. Proof. Deciding whether a Type B update takes place essentially requires a connected components computation, which accounts for O(sort(n) • log B) I/Os. Within this I/O bound we can also compute a spanning tree T s of the component holding the starting vertex s but excluding the new edge. Subsequently, there are j = O(log B) attempts, each of which uses O(sort(n)) I/Os to derive a new modified clustering based on an Euler tour with increasing chunk sizes around T s . Furthermore, before each attempt we need to initialize H and S, which takes O(sort(n)) I/Os per attempt. The worst-case number of I/Os to (re-) scan adjacency-lists in H or to explicitly fetch clusters of adjacency-lists doubles after each attempt. Therefore it asymptotically suffices to consider the (successful) last attempt j, which causes O(2 j • n/B) I/Os. Furthermore, each attempt requires another O(sort(n)) I/Os to pre-sort explicitly loaded clusters before they can be merged with H using a single scan just like in MM BFS. Adding all contributions yields the claimed I/O bound of O(2 j • n/B + sort(n) • log B) for sparse graphs.

Analysis

We split our analysis of the incremental BFS algorithm into two parts. The first (and easy one) takes care of Type A updates: Proof. Recall that d i (v), i ≥ 0, stands for the BFS level of node v if it can be reached from the source node s in G i and n otherwise. If upon the i-th update the dynamic algorithm issues an explicit fetch for the adjacency-lists of some vertex v kept in some cluster C then this is because ∆d i (v) = d i-1 (v) -d i (v) > α for the current advance α. Note that for all other vertices v ′ ∈ C, there is a path of length at most µ in G i-1 , implying that

|d i-1 (v ′ ) -d i-1 (v)| ≤ µ as well as |d i (v) -d i (v ′ )| ≤ µ. Having current chunk size µ = α/4, this implies ∆d i (v ′ ) = d i-1 (v ′ ) -d i (v ′ ) = d i-1 (v ′ ) -d i-1 (v) + d i-1 (v) -d i (v) + d i (v) -d i (v ′ ) > α -2µ ≥ α/2.
If the i-th update needs j attempts to succeed then, during the (failing) attempt j -1, it has tried to explicitly access α j-1 • n/B + 1 distinct clusters. Out of these at least α j-1 • n/B = 2 j+4 • n/B clusters carry an expected amount of at least µ j-1 /8 = 2 j-1 adjacency-lists each. This accounts for an expected number of at least 2 2•j+3 • n/B distinct vertices, each of them featuring ∆d i (•) ≥ α j-1 /2 = 2 j+3 . With probability at least 1/2 we actually get at least half of the expected amount of distinct vertices/adjacency-lists, i.e., 2 2•j+2 • n/B. Therefore, using the definitions

D i = v∈V \{s} d i (v) and ∆D i = |D i-1 -D i |,
if the i-th update succeeds within the j-th attempt we have ∆D i ≥ 2 3•j+5 • n/B =: Y j with probability at least 1/2. Let us call this event a large j-yield.

Since each attempt uses a new clustering with independent choices for r(•), if we consider two updates i ′ and i ′′ that succeed after the same number of attempts j, then both i ′ and i ′′ have a large yield with probability at least 1/2, independent of each other. Therefore, we can use Chernoff bounds [START_REF] Hagerup | A guided tour of chernoff bounds[END_REF] in order to show that out of k ≥ 16 • c • ln n updates that all succeed within their j-th attempt, at least k/4 of them have a large j-yield with probability at least 1 -n -c for an arbitrary positive constant c. Subsequently we will prove an upper bound on the total number of large j-yields that can occur during the whole update sequence.

The quantity ∆D i provides a global measure as for how much the BFS levels change after inclusion of the i-th edge from the update sequence. If there are m ′ = Θ(n) edge inserts in total, then

n 2 > D 0 ≥ D 1 ≥ . . . ≥ D m ′ -1 ≥ D m ′ > 0.
A large j-yield means ∆D i ≥ Y j . Therefore, in the worst case there are at most n 2 /Y j = n 2 /(2 3•j+5 • n/B) = n • B/2 3•j+5 large j-yield updates and -according to our discussion above -it needs at most k j := 4 • n • B/2 3•j+5 updates that succeed within the j-th attempt to have at least k j /4 large j-yield updates with high probability 2 .

For the last step of our analysis we will distinguish two kinds of Type B updates: those that finish using an advance value α j * < B 1/3 (Type B1), and the others (Type B2). Independent of the subtype, an update costs O(α j *

• n/B + sort(n) • log B) = O(2 j * • n/B + sort(n) • log B) I/Os by Lemma 4.1.
Obviously, for an update sequence of m ′ = Θ(n) edge insertions there can be at most Θ(n) updates of Type B1, each of them accounting for at most O(n/B 2/3 + sort(n) • log B) I/Os. As for Type B2 updates we have already shown that with high probability there are at most O(n • B/2 3•j * ) updates that succeed with advance value Θ(2 j * ). Therefore, using Boole's inequality, the total amount of I/Os for all Type B2 updates is bounded by

O     g≥0 n • B (B 1/3 • 2 g ) 3 • B 1/3 • 2 g • n B   + n • sort(n) • log B   = O(n • (n/B 2/3 + sort(n) • log B)) with high probability.
Combining the two lemmas of this section implies Theorem 5.3. For general sparse undirected graphs of initially n nodes and O(n) edges and Θ(n) edge insertions, dynamic BFS can be solved using amortized O(n/B 2/3 +sort(n)•log B) I/Os per update with high probability.

Decremental Version and Extensions.

Having gone through the ideas of the incremental version, it is now close to trivial to come up with a symmetric external-memory dynamic BFS algorithm for a sequence of edge deletions: instead of pre-feeding adjacency-lists into using an advance of α j levels, we now apply a lag of α j levels. Therefore, the adjacency-list for a vertex v is found in H as long as the deletion of the i-th edge does not increase d i (v) by more than α. Otherwise, an explicit random access to the cluster containing v's adjacency-list is issued later on. All previously used amortization arguments and bounds carry through, the only difference being that d i (•) values may monotonically increase instead of decrease.

Better amortized bounds can be obtained if ω(n) updates take place and/or G 0 has ω(n) edges. Then we have the potential to amortize more random accesses per attempt, which leads to larger j-yields and reduces the worst-case number of expensive updates. Consequently, we can reduce the defining threshold between Type B1 and Type B2 updates, 2 We also need to verify that kj ≥ 16 • c • ln n. As observed before, the dynamic algorithm will not thus eventually yielding better amortized I/O bounds. Details we be provided in the full version of this paper. Modifications along similar lines are in order if external-memory is realized by flash disks [START_REF] Gal | Algorithms and data structures for flash memories[END_REF]: compared to hard disks, flash memory can sustain many more unstructured read I/Os per second but on the other hand flash memory usually offers less read/write bandwidth than hard disks. Hence, in algorithms like ours that are based on a trade-off between unstructured read I/Os and bulk read/write I/Os, performance can be improved by allowing more unstructured read I/Os (fetching clusters) if this leads to less overall I/O volume (scanning hot pool entries).

Conclusions

We have given the first non-trivial external-memory algorithm for dynamic BFS. Even though we obtain significantly better I/O bounds than for the currently best static algorithm, there are a number of open problems: first of all, our bounds dramatically deteriorate for mixed update sequences (edge insertions and edge deletions in arbitrary order and proportions); besides oscillation effects, a single edge deletion (insertion) may spoil a whole chain of amortizations for previous insertions (deletions). Also, it would be interesting to see, whether our bounds can be further improved or also hold for shorter update sequences. Finally, it would be nice to come up with a deterministic version of the modified clustering.

Lemma 4 . 1 .

 41 For sparse graphs with O(n) updates, each Type B update succeeding during the j-th attempt requires O(2 j • n/B + sort(n) • log B) I/Os.

Lemma 5 . 1 .

 51 For sparse undirected graphs with Θ(n) updates, there are at most n -1 Type A updates causing O(n • sort(n) • log B) I/Os in total. Proof. Each Type A update starts with an EM connected components computation causing O(sort(n) • log B) I/Os per update. Since each node can be added to the connected component C s holding the starting vertex s only once, the total number of I/Os spend in calls to the MR-BFS algorithm on components to be merged with C s is O(n + sort(n)). Producing the output takes another O(sort(n)) per update. Now we turn to Type B updates: Lemma 5.2. For sparse undirected graphs with Θ(n) updates, all Type B updates cause O(n • (n 2/3 + sort(n) • log B)) I/Os in total with high probability.

  increase its advance and chunk size values beyond O(√ B) implying 2 j = O( √ B). But then we have kj = 4 • n • B/2 3•j+5 = Ω(n/ √ B) and n/ √ B ≥ n/ √ M ≥ n/ √ n ≥ 16 • c • ln n for sufficiently large n.

The last chunk of the Euler tour only visits ((2 • n ′ -1) mod µ) + 1 vertices where n ′ denotes the number of vertices in the connected component of the starting node s.

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.

Acknowledgements

We would like to thank Deepak Ajwani for very helpful discussions.

Partially supported by the DFG grant ME 3250/1-1, and by the center of massive data algorithmics (MADALGO) funded by the Danish National Research Foundation. c U. Meyer