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

In this paper we introduce "hybrid" Max 2-CSP formulas consisting of "simpleclauses", namely conjunctions and disjunctions of pairs of variables, andgeneral 2-variable clauses, which can be any integer-valued functions of pairsof boolean variables. This allows an algorithm to use both efficient reductionsspecific to AND and OR clauses, and other powerful reductions that require thegeneral CSP setting. We use new reductions introduced here, and recentreductions such as "clause-learning" and "2-reductions" generalized to oursetting's mixture of simple and general clauses.  Parametrizing an instance by the fraction p of non-simple clauses, we give anexact (exponential-time) algorithm that is the fastest known polynomial-spacealgorithm for p=0 (which includes the well-studied Max 2-Sat problem but alsoinstances with arbitrary mixtures of AND and OR clauses); the only efficientalgorithm for mixtures of AND, OR, and general integer-valued clauses; and tiedfor fastest for general Max 2-CSP (p=1). Since a pure 2-Sat input instance maybe transformed to a general CSP instance in the course of being solved, thealgorithm's efficiency and generality go hand in hand.  Our algorithm analysis and optimization are a variation on the familiarmeasure-and-conquer approach, resulting in an optimizing mathematical programthat is convex not merely quasi-convex, and thus can be solved efficiently andwith a certificate of optimality. We produce a family of running-timeupper-bound formulas, each optimized for instances with a particular value of pbut valid for all instances.

A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between