As a guest user you are not logged in or recognized by your IP address. You have
access to the Front Matter, Abstracts, Author Index, Subject Index and the full
text of Open Access publications.
Minimizing a cost function under a set of combinatorial constraints is a fundamental, yet challenging problem in AI. Fortunately, in various real-world applications, the set of constraints describing the problem structure is much less susceptible to change over time than the cost function capturing user's preferences. In such situations, compiling the set of feasible solutions during an offline step can make sense, especially when the target compilation language renders computationally easier the generation of optimal solutions for cost functions supplied “on the fly”, during the online step. In this paper, the focus is laid on Boolean constraints compiled into DNNF representations. We study the complexity of the minimization problem for several families of cost functions subject to DNNF constraints. Beyond linear minimization which is already known to be tractable in the DNNF language, we show that both quadratic minimization and submodular minization are fixed-parameter tractable for various subsets of DNNF. In particular, the fixed-parameter tractability of constrained submodular minimization is established using a natural parameter capturing the structural dissimilarity between the submodular cost function and the DNNF representation.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.