Challenges in Competitive Online Optimisation (CCOO)

Online decision-making, characterised by the need to make immediate decisions without knowledge of the future, lies at the heart of numerous applications. Yet our understanding of dealing with the resulting uncertainty remains poor. Through the lens of the established framework of online algorithms as well as the emerging field of learning-augmented algorithms, this project aims to address central challenges in decision-making under uncertainty.

While there has been extensive research on online algorithms, many of the core challenges remain unresolved. However, several recent discoveries of novel algorithmic design and analysis techniques have opened up new avenues for overcoming previous obstacles.

In parallel, the rise of machine learning is now dramatically enriching our tool-set for dealing with uncertainty. This has motivated the recent emergence of the field of learning-augmented algorithms. Here, an algorithm's input is augmented with predictions, aiming for near-optimal performance if predictions are reasonably good, while still retaining classical worst-case guarantees even for highly erroneous predictions.

Inspired by these recent developments, this project aims to substantially elevate our understanding of decision-making under uncertainty.

The main objectives are:

1. To explore new directions around the concept of work functions.
2. To elevate the mirror descent technique to a generic tool for online algorithm design.
3. To develop universal techniques for designing learning-augmented algorithms.
4. To expand the scope of learning-augmented algorithms to new domains.

The project addresses questions at the forefront of theoretical computer science, building on Christian Coester's recent success in resolving several long-standing problems, and strives for foundational contributions to the timely issue of leveraging machine learning for improved algorithm design.