A study on clustering algorithms with predictions

Most of the well known and state-of-the-art algorithms have great performances in their best-case scenarios, both in terms of time complexity and of quality of the solution. However, worst-case scenarios still may happen and represent a limit hard to bypass. For this reason a whole new approach was born, combining algorithms with machine learning, and it is called "algorithms with predictions". In this thesis we focus on the k-means problem and its two most used algorithms, kmeans++ and Lloyd's (algorithm), studying and experimenting new ideas that may lead to new approaches to solve this problem using machine learning.