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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Let F be a CNF formula with n variables and m clauses. F is tsatisfiable if for any t clauses in F, there is a truth assignment which satisfies all of them. Lieberherr and Specker (1982) and, later, Yannakakis (1994) proved that in each 3-satisfiable CNF formula at least 2/3 of its clauses can be satisfied by a truth assignment. Yannakakis's proof utilizes the fact that 2/3m is a lower bound on the expected number of clauses satisfied by a random truth assignment over a certain distribution. A CNF formula F is called expanding if for every subset X of the variables of F, the number of clauses containing variables of X is not smaller than |X|. In this paper we strengthen the 2/3m bound for expanding 3- satisfiable CNF formulas by showing that for every such formula F at least 2 3m+ρn clauses of F can be satisfied by a truth assignment, where ρ( 0.0019) is a constant. Our proof uses a probabilistic method with a sophisticated distribution for truth values. We use the bound 2 3m + ρn and results on matching autarkies to obtain a new lower bound on the maximum number of clauses that can be satisfied by a truth assignment in any 3-satisfiable CNF formula. We use our results above to show that the following parameterized problem is fixed-parameter tractable and, moreover, has a kernel with a linear number of variables. In 3-S-MAXSAT-AE, we are given a 3-satisfiable CNF formula F with m clauses and asked to determine whether there is an assignment which satisfies at least 2 3m + k clauses, where k is the parameter. Note that Mahajan and Raman (1999) asked whether 2-S-MAXSAT-AE, the corresponding problem for 2-satisfiable formulas, is fixed-parameter tractable. Crowston and the authors of this paper proved in [9] that 2-S-MAXSAT-AE is fixed-parameter tractable and, moreover, has a kernel with a linear number of variables. 2-S-MAXSAT-AE appears to be easier than 3-S-MAXSAT-AE and, unlike this paper, [9] uses only deterministic combinatorial arguments.

A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application