Expressing and Supporting Efficiently Greedy Algorithms as Locally Stratified Logic Programs.
Carlo Zaniolo · 2015
The problem of expressing and supporting classical greedy algorithms in Datalog has been the focus of many significant research efforts that have produced very interesting solutions for particular algorithms. But we still lack a general treatment that characterizes the relationship of greedy algorithms to non-monotonic theories and leads to asymptotically optimal implementations. In this paper, we propose a general solution to this problem. Our approach begins by identifying a class of locally stratified programs that subsumes XY-stratified programs and is formally characterized using the Datalog1S representation of numbers. Then, we propose a simple specialization of the iterated fixpoint procedure that computes efficiently the perfect model for these programs, achieving optimal asymptotic complexities for well-known greedy algorithms.This makes possible their efficient support in Datalog systems.