Abstract
Dynamic programming is a well-known technique for computing the best solution to various optimization problems and, in particular, to problems expressed via semirings. The question we ask in this talk is what if we want the 2nd-best, 3rd-best, and so on, solution to such a problem? Ranked enumeration solves precisely this problem by returning the solutions one-by-one in the order dictated by a ranking function. We will review the history of algorithms for this task, the properties of the ranking function (and the properties of the corresponding semiring) that allow for efficient computation, and the application to Conjunctive Queries, which allows a database to return the set of answers as a sorted stream.
Project Website: https://northeastern-datalab.github.io/anyk/