Zoltán Király:
Online and parallel algorithms
Online algorithms.
An online algorithm is one that can process its input piece-by-piece
in a serial fashion, i.e., in the order that the input is fed to the
algorithm, without having the entire input available from the
start. We are mainly interested in the competitiveness of an online
algorithm which is defined by the ratio of its cost and the optimal
offline cost (on the worst input).
After looking at some examples, we
focus on two important problems: paging (with a cache of size k), and
k-robots in a metric space. For both problems, we prove that no online
algorithm can exist which is better than k-competitive. We also show
online algorithms for paging and for a restricted version of the
k-robot problem that are k-competitive.
Parallel algorithms. We concentrate on the following
problem. Suppose you have a very good laptop with 128 CPU cores. Will
your algorithms run 128 times faster? The answer is NO in most
cases. A better question: can you design a new algorithm for your
given problem that runs at least 64 times faster?
We shortly discuss some basic models of parallel computation. Afterward we learn some basic parallel algorithms for the following problems.
- Adding and multiplying two huge numbers.
- Constructing a 3 log L deep algebraic tree for an algebraic formula of length L
- Calculating shortest paths in graphs