A study on Online Minimum Spanning Tree Algorithms with Predictions

The minimim spanning tree problem is an important problem in the field of graph theory and computer science, due to its many applications. A natural evolution of the problem is to consider it in the online setting, where the true weights on the edges arrive one at the time. In this setting it is proven the there is no deterministic algorithm that is competitive, consequently alternative solutions are needed. In this study we considered the algorithms with predictions introduced by Berg et al. (2023), called Follow-the-Predictions (FtP) and Greedy-Follow-the-Predictions (GFtP) algorithms, for the online minimum spanning tree problem. We provided an implementation for the algorithms and we tested them through a series of experiments to try to understand their behavior. We tested the robustness of these algorithms according to the variations of accuracy of predictor, and how the results would transfer when using a real predictor. The experiments we conducted highlighted that the GFtP algorithm tends to perform better than the FtP algorithm under increasing error in the predictions when using a controlled predictor, while this characteristic is not always true when we use a real predictor. Another experiment showed that the GFtP algorithm is extremely sensitive to over- and under estimation from the predictor, limiting the situations in which this algorithm is an actual improvement. Thanks to the applications of machine learning predictions for the problem, we were able to effectively apply an algorithm with predictions for the online minimum spanning tree problem in a real case, and obtained competitive results, which would have been otherwise impossible.

Il minimum spanning tree problem è un problema importante nel campo della teoria dei grafi e in computer science, grazie alle sue numerose applicazioni. Un’evoluzione naturale del problema è considerarlo in un contesto online, in cui i pesi reali sugli archi arrivano uno alla volta. In questo scenario è stato dimostrato che non esiste un algoritmo deterministico competitivo, rendendo necessarie soluzioni alternative. In questo studio abbiamo considerato gli algoritmi con predizioni introdotti in Berg et al. (2023), chiamati Follow-the-Predictions (FtP) e Greedy-Follow-the Predictions (GFtP), per il problema dell’online minimum spanning tree. Abbiamo fornito un’implementazione di questi algoritmi e li abbiamo testati attraverso una serie di esperimenti per comprenderne il comportamento. Abbiamo analizzato la robustezza di questi algoritmi rispetto alle variazioni di accuratezza del predittore e come i risultati si trasferissero utilizzando un predittore reale. Gli esperimenti condotti hanno evidenziato che l’algoritmo GFtP tende a ottenere prestazioni migliori rispetto all’algoritmo FtP all’aumentare dell’errore nelle predizioni, quando viene utilizzato un predittore controllato, mentre questa caratteristica non è sempre vera quando si utilizza un predittore reale. Un altro esperimento ha mostrato che l’algoritmo GFtP è estremamente sensibile a sovrastime e sottostime da parte del predittore, limitando le situazioni in cui questo algoritmo rappresenta un effettivo miglioramento. Grazie all’applicazione delle predizioni basate sul machine learning al problema, siamo stati in grado di applicare efficacemente un algoritmo con predizioni per il problema dell’online minimum spanning tree in un caso reale, ottenendo risultati competitivi che altrimenti sarebbero stati impossibili.