Skip to yearly menu bar Skip to main content


Poster

Learning-Augmented Priority Queues

Ziyad Benomar · Christian Coester

[ ]
Thu 12 Dec 11 a.m. PST — 2 p.m. PST

Abstract:

Priority queues are one of the most fundamental and widely used data structures in computer science. Their primary objective is to efficiently support the insertion of new elements with assigned priorities and the extraction of the highest priority element. In this study, we investigate the design of priority queues within the learning-augmented framework, where algorithms use potentially inaccurate predictions to enhance their worst-case performance.We examine three prediction models spanning different use cases, and we show how the predictions can be leveraged to enhance the performance of priority queue operations. Moreover, we demonstrate the optimality of our solution and discuss some possible applications.

Live content is unavailable. Log in and register to view live content