On the stability of dynamic diffusion load balancing. (2008)
Berenbrink, P., Friedetzky, T., Martin, R.
We consider the problem of dynamic load balancing in arbitrary (connected) networks on n nodes. Our load generation model is such that during each round, n tasks are generated on arbitrary nodes, and...
Distributed selfish load balancing. (2006)
Berenbrink, P., Friedetzky, T., Goldberg, L. A., Goldberg, P., Hu, Z., Martin, R.
Suppose that a set of m tasks are to be shared as equally as possible amongst a set of n resources. A game-theoretic mechanism to find a suitable allocation is to associate each task with a "selfish...
Distributed selfish load balancing. (2006)
Berenbrink, P., Friedetzky, T., Goldberg, L. A., Goldberg, P., Hu, Z., Martin, R.
Suppose that a set of m tasks are to be shared as equally as possible amongst a set of n resources. A game-theoretic mechanism to find a suitable allocation is to associate each task with a "selfish...
Finding frequent patterns in a string in sublinear time. (2005)
Berenbrink, P., Ergun, F., Friedetzky, T.
We consider the problem of testing whether (a large part of) a given string X of length n over some finite alphabet is covered by multiple occurrences of some (unspecified) pattern Y of arbitrary...
Dynamic diffusion load balancing. (2005)
Berenbrink, P., Friedetzky, T., Martin, R.
We consider the problem of dynamic load balancing in arbitrary (connected) networks on n nodes. Our load generation model is such that during each round, n tasks are generated on arbitrary nodes, and...
The natural work-stealing algorithm is stable. (2003)
Berenbrink, P., Friedetzky, T., Goldberg, L. A.
In this paper we analyze a very simple dynamic work-stealing algorithm. In the work-generation model, there are n (work) generators. A generator-allocation function is simply a function from the n...