Roderick Sebastiaan de Nijs, Christian Landsiedel, Dirk Wollherr and Martin Buss (2016) "Quadratization and Roof Duality of Markov Logic Networks", Volume 55, pages 685-714

PDF | doi:10.1613/jair.5023

This article discusses the quadratization of Markov Logic Networks, which enables efficient approximate MAP computation by means of maximum flows. The procedure relies on a pseudo-Boolean representation of the model, and allows handling models of any order. The employed pseudo-Boolean representation can be used to identify problems that are guaranteed to be solvable in low polynomial-time. Results on common benchmark problems show that the proposed approach finds optimal assignments for most variables in excellent computational time and approximate solutions that match the quality of ILP-based solvers.

Click here to return to Volume 55 contents list