On the exponential potential for analysing algorithms with dynamic data

23^rd April 2024, 13:00 Ashton Lecture Theatre
Dr. Dimitrios Los
Department of Computer Science and Technology, University of Cambridge

Abstract

In this talk I will present some techniques to analyse algorithms with dynamic data using exponential potential functions. More specifically, I will show how these techniques can be applied to analyse balanced allocations processes and sorting algorithms where the data is evolving.

In the balanced allocations setting we need to allocate $m$ balls into $n$ bins with the aim to minimise the maximum load. In a centralised setting, Round-Robin trivially achieves the optimal maximum load. In a decentralised setting, the $d$-Choice algorithm has proven particularly effective; sampling $d$ bins uniformly at random and allocating to the one with the least load. It is well-known that for $m \gg n$ and $d=1$ the maximum load is $m/n + \Theta(\sqrt{m/n \cdot \log n})$, while for $d = 2$, it is $m/n + \Theta(\log \log n)$, a striking difference known as the ``power of two choices''. I will outline how a small set of techniques can be used to analyse a wide range of algorithms and settings with noise and outdated information.

In sorting with evolving data, every step of the comparison-based sorting algorithm is followed by $b$ steps where two elements of adjacent ranks are swapped. The aim is to maintain a permutation that is close in terms of $\ell_1$-distance to the sorted permutation. I will show how a carefully designed exponential potential function can be used to analyse randomised bubble sort, resolving an open problem.

If time permits, I will briefly talk about the time complexity of simulating balanced allocation processes.

(Based on joint work with G. Giakkoupis, M. Kiwi, T. Sauerwald and J. Sylvester)