Algoritmi con predizioni per code con priorità e clustering

In recent years, the evolution of the computer science field has fostered a growing interest in algorithms capable of dynamically adapting to large volumes of incoming data by leveraging additional information to optimize performance. Within this context, the innovative approach of algorithms with prediction emerges, aiming to integrate predictive models into traditional data structures and algorithms, with the objective of reducing the number of computationally expensive operations and improving overall performance. This thesis aims to analyze the performance of algorithms with predictions applied both to the management of Priority Queues and to the resolution of the k-center clustering problem through the Farthest-First Traversal algorithm. The analysis initially focuses on the design of priority queues within three learning-augmented frameworks, each characterized by different prediction models. Through complexity analysis, it is demonstrated how the accuracy of predictions can influence the improvement of algorithmic performance, while ensuring worst-case behavior comparable to that of traditional algorithms. Subsequently, the Farthest-First Traversal algorithm is examined a coreset-based, 2-round MapReduce implementation within a learning-augmented framework capable of estimating the distance between two elements. The relationship between the accuracy of the prediction algorithm and the quality of the resulting output is then evaluated. The analysis and discussion of the presented algorithms are supported by average-case proofs, along with an in-depth study of the generalization of the approximated distance in the Farthest-First Traversal algorithm.

Negli ultimi anni, l'evoluzione del settore informatico ha stimolato un crescente interesse verso algoritmi capaci di adattarsi dinamicamente a grandi quantità di dati in ingresso, sfruttando informazioni supplementari per ottimizzare le prestazioni. In tale contesto si inserisce l'approccio innovativo degli algoritmi con predizione, finalizzato all'integrazione di modelli predittivi all'interno di strutture dati e algoritmi tradizionali, con l'obiettivo di ridurre il numero di operazioni computazionalmente onerose e ottimizzare le prestazioni complessive. Questa tesi si propone di analizzare le prestazioni di algoritmi con predizioni applicati sia alla gestione di Priority Queue sia alla risoluzione, mediante l'algoritmo Farthest-First Traversal, del problema di k-center clustering. L'analisi si concentra inizialmente sulla progettazione di code di priorità all'interno di tre framework di apprendimento potenziato, ciascuno caratterizzato da modelli di predizione differenti. Dall'analisi della complessità si riesce a dimostrare come la precisione delle previsioni possa influenzare il miglioramento delle prestazioni degli algoritmi, garantendo nel caso peggiore livelli comparabili a quelli degli algoritmi tradizionali. Successivamente viene esaminato l'algoritmo Farthest-First Traversal, coreset-based con MapReduce a 2 round, implementato all'interno di un framework di apprendimento potenziato in grado di fornire una stima della misura di distanza tra due elementi. Viene quindi valutata la relazione tra la precisione dell'algoritmo di predizione e la qualità del risultato ottenuto. L'analisi e la trattazione degli algoritmi presentati vengono sostenute attraverso dimostrazioni al caso medio, con l'aggiunta di un approfondimento sulla generalizzazione della distanza approssimata nell'algoritmo Farthest-First Traversal.