Publication Details
Title: Probabilistic Recurrence Relations for Parallel Divide-and-Conquer Algorithms
Author: M. Karpinski and W. Zimmermann
Group: ICSI Technical Reports
Date: December 1991
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-067.pdf
Overview:
We study two probabilistic recurrence relations that arise frequently in the analysis of parallel and sequential divide-and-conquer algorithms (cf. [Karp 91]). Suppose a problem of size x has to be solved. In order to solve it we divide it into subproblems of size h_1(x), ... ,h_k(x) and these subproblems are solved recursively. We assume that size(h_i(z)) are random variables. This occurs if either the break up step is randomized or the instances to be solved are drawn from a probability distribution. The running time T(z) of a parallel algorithm is therefore determined by the maximum of the running times T(h_i(z)) of the subproblems while the sequential algorithm is determined by the sum of the running times of the subproblems. We give a method for estimating tight upper bounds on the probability distribution of T(x) for these two kinds of recurrence relations, answering the open questions in [Karp 91]. Keywords: Probabilistic Recurrence Relations, Devide-and-Conquer Algorithms, Parallel Algorithms, Upper Bounds on Probability Distribution.
Bibliographic Information:
ICSI Technical Report TR-91-067
Bibliographic Reference:
M. Karpinski and W. Zimmermann. Probabilistic Recurrence Relations for Parallel Divide-and-Conquer Algorithms. ICSI Technical Report TR-91-067, December 1991
Author: M. Karpinski and W. Zimmermann
Group: ICSI Technical Reports
Date: December 1991
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1991/tr-91-067.pdf
Overview:
We study two probabilistic recurrence relations that arise frequently in the analysis of parallel and sequential divide-and-conquer algorithms (cf. [Karp 91]). Suppose a problem of size x has to be solved. In order to solve it we divide it into subproblems of size h_1(x), ... ,h_k(x) and these subproblems are solved recursively. We assume that size(h_i(z)) are random variables. This occurs if either the break up step is randomized or the instances to be solved are drawn from a probability distribution. The running time T(z) of a parallel algorithm is therefore determined by the maximum of the running times T(h_i(z)) of the subproblems while the sequential algorithm is determined by the sum of the running times of the subproblems. We give a method for estimating tight upper bounds on the probability distribution of T(x) for these two kinds of recurrence relations, answering the open questions in [Karp 91]. Keywords: Probabilistic Recurrence Relations, Devide-and-Conquer Algorithms, Parallel Algorithms, Upper Bounds on Probability Distribution.
Bibliographic Information:
ICSI Technical Report TR-91-067
Bibliographic Reference:
M. Karpinski and W. Zimmermann. Probabilistic Recurrence Relations for Parallel Divide-and-Conquer Algorithms. ICSI Technical Report TR-91-067, December 1991