Beyond worst-case analysis, with or without predictions

In this thesis we design online combinatorial optimization algorithms for beyond worst-case analysis settings.

In the first part, we discuss the online matching problem and prove that, in the edge arrival model, no online algorithm can achieve a competitive ratio better than $\nicefrac{1}{2} + c$ for any constant $c > 0$. This result serves as an illustrative example to showcase the limitations of worst-case analysis.

The second and third parts introduce the concept of learning-augmented algorithms, which leverage predictions about the input to enhance their performance. The learning-augmented algorithms developed in those parts exhibit improved performance when predictions are accurate, while also demonstrating robustness even in the presence of misleading predictions.

In the second part, we investigate the online speed scheduling problem for energy minimization. We design an algorithm that incorporates predictions about future requests in a black-box manner and surpasses known lower-bounds of classical online algorithms when the predictions are accurate, while still maintaining robustness when predictions are incorrect.

The third part extends the Primal-Dual method from the classical online algorithms setting to the learning-augmented setting. We apply this technique to various problems, including online set cover, ski rental, TCP acknowledgment, and Bahncard.

Finally, in the fourth part, we delve into the correlation clustering problem in the online with recourse model. While the classical online setting is too restrictive and strong impossibility results make the problem uninteresting, in the recourse model we present an algorithm that achieves a worst-case logarithmic recourse with constant competitive ratio.