Networks

The stability of online algorithms

Summary Online algorithms are traditionally analyzed with respect to their competitive ratio. In this research project we investigate,  for various basic optimization problems, the trade-off that exists between the competitive ratio on the one hand, and the so-called stability of a solution on the other hand. The concept of stability captures the similarity between consecutive solutions outputted by the online algorithm, and can be quantified in various ways. This concept is important when solutions have to be maintained over time. By establishing lower and upper bounds on this trade-off, we aim to get better insight in the performance of online algorithms that output solutions that are maintained over time 
Supervisors Frits Spieksma (TU Eindhoven and Mark de Berg (TU Eindhoven) 
PhD Student Andrés López Martínez
Location Eindhoven University of Technology (TU/e)