Greedy Algorithms in Datalog

Title: Greedy Algorithms in Datalog

Research Question: How can we express and implement greedy algorithms using declarative logic-based languages like Datalog, while maintaining their efficiency?

Methodology: The authors propose extending the framework of Datalog-like languages to create simple declarative formulations for greedy algorithms. They introduce primitives for choice and greedy selection, and show how to translate programs with such constructs to programs that only use negation as a non-monotonic construct. They also define classes of programs with these constructs and demonstrate that these programs have stable model semantics, are identifiable at compile time, and can be optimized for efficient execution.

Results: The authors show that their approach allows for the expression of many non-deterministic decision problems using nondeterministic constructs in logic programs. They provide examples of how to implement greedy algorithms using their proposed primitives and demonstrate that these implementations maintain the same complexities as those expected from greedy algorithms in procedural programs.

Implications: The authors' work has several implications for the field. First, it provides a programmer with declarative tools to express greedy algorithms, freeing them from many implementation details while guaranteeing good performance. Second, it contributes to the ongoing research on expressing and implementing non-deterministic decision problems in logic-based languages. Lastly, it may lead to new insights and developments in the field of declarative programming and logic programming.

Link to Article: https://arxiv.org/abs/0312041v1 Authors: arXiv ID: 0312041v1