Advances in Online Algorithms

Algorithms are a fundamental concept in computer science. In the classical view of computation, we are presented with the input to a problem, on which a computer performs a sequence of computations to produce a solution. However, depending on various computational restrictions, such a solution may not necessarily be optimal.

One such restricted setting is that of online problems, in which the problem input is not presented entirely up front, but rather revealed sequentially, requiring the algorithm to produce intermediate solutions based only on past and present data. Past decisions of the algorithm are irrevocable and may lead to suboptimal solutions. Indeed, in general we can only hope for an algorithm which produces solutions with cost only so many times larger than the cost of the optimal offline solution. We quantify this with the competitive ratio, which is the most commonly used measure of the performance of an online algorithm.

The aim of our research is to make significant advances in the design and rigorous mathematical analysis of algorithms for central problems in computer science, with a specific focus on online algorithms. We will also explore related topics in approximation and streaming algorithms.

A specific example of an interesting problem is the reordering buffer management problem. Here a server must process a sequence of requests, corresponding to points in a metric space (which can be thought of as some sort of map), and the algorithm aims to minimise the total distance travelled by the server moving between each request. To enable the server to travel a smaller distance, the algorithm may store a fixed number of requests at a time in a buffer, from which it can choose to serve requests in any order. The main question is how this order should be chosen.

This problem has been studied extensively and good algorithms are known. However, many open questions remain. For instance, this result produces a competitive ratio which depends on properties of the metric space, including its size. Removing these dependencies would be a significant achievement. Additionally, a relatively recent breakthrough result on the well-known k-server problem involves a novel application of a mirror descent technique, resulting in a significantly improved competitive ratio. We are interested in exploring the potential of this technique further, in particular in connection to the reordering buffer problem.

Further problems of interest for this project include online matching, packet buffer management, and submodular maximisation in streaming.

Alignment with EPSRC research areas: Theoretical Computer Science, Operational Research, ICT Networks & Distributed Systems, Statistics and Applied Probability.