Any-k: Ranked Enumeration for Dynamic Programming

Explore the concept of ranked enumeration for dynamic programming in this 32-minute lecture by Nikos Tziavelis from Northeastern University. Delve into the challenge of finding not just the best solution to optimization problems, but also the 2nd-best, 3rd-best, and beyond. Examine the history of algorithms for this task, the crucial properties of ranking functions and semirings that enable efficient computation, and discover how this approach applies to Conjunctive Queries in databases. Learn how ranked enumeration allows for returning solutions one-by-one in a specified order, providing a powerful tool for optimization problems expressed via semirings. Gain insights into how this technique can be used to return database query answers as a sorted stream.

Any-k: Ranked enumeration for Dynamic Programming