Poster
Sorting with Predictions
Xingjian Bai · Christian Coester
Great Hall & Hall B1+B2 (level 1) #529
Abstract:
We explore the fundamental problem of sorting through the lens of learning-augmented algorithms, where algorithms can leverage possibly erroneous predictions to improve their efficiency. We consider two different settings: In the first setting, each item is provided a prediction of its position in the sorted list. In the second setting, we assume there is a quick-and-dirty'' way of comparing items, in addition to slow-and-exact comparisons. For both settings, we design new and simple algorithms using only exact comparisons, where is a suitably defined prediction error for the th element. In particular, as the quality of predictions deteriorates, the number of comparisons degrades smoothly from to . We prove that this comparison complexity is theoretically optimal with respect to the examined error measures. An experimental evaluation against existing adaptive and non-adaptive sorting algorithms demonstrates the potential of applying learning-augmented algorithms in sorting tasks.
Chat is not available.