Sorting and Priority Queues with Predictions
The talk discusses two of the most fundamental problems in algorithms and data structures through the lens of algorithms-with-predictions / learning-augmented algorithms: sorting and priority queues. We consider different types of predictions and show how these can be used to improve running time and comparison complexity of algorithms. In one setting, the algorithm is given predictions about the rank of items, and in another setting, the algorithm has access to quick-and-dirty comparisons to complement much slower exact comparisons. We obtain simple algorithms with optimal guarantees and favorable experimental performance in sorting tasks as well as when applied to Dijkstra’s shortest path algorithm.
Based on joint works with Xingjian Bai and Ziyad Benomar.