We study the applicability of randomized methods for parallel processing. There are at least two motivations to consider parallel algorithms which follow some sort of probabilistic approach. A first motivation is the fact that randomized solutions have often a simpler structure than that of deterministic solutions which are presently available. Moreover, there are some important problems in combinatorial optimization, like matching problems in graphs and those related to them (like network-flow problems), Shortest Path Computations, Breadth and Depth First Search, whose known deterministic parallel algorithms require significantly more running time and more work complexity. Furthermore, in some cases, like matching problems, randomized techniques are the only known methods which provide parallel algorithms running in polylogarithmic time and using a polynomial number of processors.

We intend to present a few examples to illustrate some important randomized techniques that have been fruitfully applied in the design of parallel algorithms. Thus, the aim is to give simple algorithms which represent well the key ideas of such techniques rather than the detailed description of the most efficient algorithms in the literature (about the latter we will give an updated bibliography). Finally, we show some derandomization methods for probablistic algorithms.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing