Publication

Beyond worst-case analysis, with or without predictions

Andreas Maggiori
2023
EPFL thesis
Abstract

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 \nicefrac12+c\nicefrac{1}{2} + c for any constant c>0c > 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.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related concepts (36)
Competitive analysis (online algorithm)
Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance. An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded.
Online algorithm
In computer science, 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. In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand. In operations research, the area in which online algorithms are developed is called online optimization.
Genetic algorithm
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection. Some examples of GA applications include optimizing decision trees for better performance, solving sudoku puzzles, hyperparameter optimization, causal inference, etc.
Show more
Related publications (32)

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Mehmet Fatih Sahin

Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...
EPFL2023

Thermal Design of a Medium Voltage Modular Multilevel Converter Cell

Drazen Dujic, Yanick Patrick Frei

This paper presents the cooling concept for a medium voltage modular multilevel converter cell. To optimize power density, the metallic enclosure is used to dissipate the heat generated by semiconductor losses, while maintaining maximum temperatures below ...
IEEE2023

Policy-based Exploration of Equilibrium Representations (PEER): A topology grammar for generative conceptual structural design

Ioannis Mirtsopoulos

Design exploration is a creative process that consists of the incremental generation of design candidates. Supported by digital means or not, the process handles the ill-structured nature of design and allows creativity to flourish through diversity of des ...
EPFL2022
Show more