English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Tree projections provide a unifying framework to deal with most structuraldecomposition methods of constraint satisfaction problems (CSPs). Within thisframework, a CSP instance is decomposed into a number of sub-problems, calledviews, whose solutions are either already available or can be computedefficiently. The goal is to arrange portions of these views in a tree-likestructure, called tree projection, which determines an efficiently solvable CSPinstance equivalent to the original one. Deciding whether a tree projectionexists is NP-hard. Solution methods have therefore been proposed in theliterature that do not require a tree projection to be given, and that eithercorrectly decide whether the given CSP instance is satisfiable, or return thata tree projection actually does not exist. These approaches had not beengeneralized so far on CSP extensions for optimization problems, where the goalis to compute a solution of maximum value/minimum cost. The paper fills thegap, by exhibiting a fixed-parameter polynomial-time algorithm that eitherdisproves the existence of tree projections or computes an optimal solution,with the parameter being the size of the expression of the objective functionto be optimized over all possible solutions (and not the size of the wholeconstraint formula, used in related works). Tractability results are alsoestablished for the problem of returning the best K solutions. Finally,parallel algorithms for such optimization problems are proposed and analyzed.Given that the classes of acyclic hypergraphs, hypergraphs of boundedtreewidth, and hypergraphs of bounded generalized hypertree width are allcovered as special cases of the tree projection framework, the results in thispaper directly apply to these classes. These classes are extensively consideredin the CSP setting, as well as in conjunctive database query evaluation andoptimization.

Tree Projections and Constraint Optimization Problems: Fixed-Parameter Tractability and Parallel Algorithms