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