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

Valued constraint satisfaction problems (VCSPs) are a large class ofcombinatorial optimisation problems. It is desirable to classify thecomputational complexity of VCSPs depending on a fixed set of allowed costfunctions in the input. Recently, the computational complexity of all VCSPs forfinite sets of cost functions over finite domains has been classified in thissense. Many natural optimisation problems, however, cannot be formulated asVCSPs over a finite domain. We initiate the systematic investigation ofinfinite-domain VCSPs by studying the complexity of VCSPs for piecewise linearhomogeneous cost functions. We show that such VCSPs can be solved in polynomialtime when the cost functions are additionally submodular, and that this isindeed a maximally tractable class: adding any cost function that is notsubmodular leads to an NP-hard VCSP.

Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains