Search
Search Results
-
On MAX–SAT with Cardinality Constraint
We consider the weighted MAX–SAT problem with an additional constraint that at most k variables can be set to true. We call this problem k...
-
Max-SAT with Cardinality Constraint Parameterized by the Number of Clauses
Max-SAT with cardinality constraint (CC-Max-SAT) is one of the classical NP-complete problems. In this problem, given a CNF-formula...
-
A Proof Builder for Max-SAT
Complete Max-SAT solvers are able to return the optimal value of an input instance but they do not provide any certificate of its validity. In this...
-
Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization
We introduce a novel approach to translate arbitrary 3-sat instances to Quadratic Unconstrained Binary Optimization (qubo) as they are used by...
-
Stochastic local search for Partial Max-SAT: an experimental evaluation
Stochastic local search (SLS) methods are heuristic-based algorithms that have gained in popularity for their efficiency and robustness when solving...
-
Maximizing a deep submodular function optimization with a weighted MAX-SAT problem for trajectory clustering and motion segmentation
Computer vision models are commonly defined for maximum constrained submodular functions lies at the core of low-level and high-level models. In such...
-
Sublinear-Space Approximation Algorithms for Max r-SAT
In the \(\textsc {Max}\ r\text {-}\textsc {SAT}{}\)...
-
A Novel Algorithm for Max Sat Calling MOCE to Order
In this paper, we present and study a new algorithm for the Maximum Satisfiability (Max Sat) problem. The algorithm, GO-MOCE, is based on the Method...
-
Reasoning and inference for (Maximum) satisfiability: new insights
At the heart of computer science and artificial intelligence, logic is often used as a powerful language to model and solve complex problems that...
-
Function Synthesis for Maximizing Model Counting
Given a boolean formula \(\phi (X, Y, Z)\) , the...
-
Reduction-Based MAX-3SAT with Low Nonlinearity and Lattices Under Recombination
A new construction is introduced for creating random MAX-3SAT instances with low nonlinearity. Instead of generating random clauses, we generate...
-
Global Landscape Structure and the Random MAX-SAT Phase Transition
We revisit the fitness landscape structure of random MAX-SAT instances, and address the question: what structural features change when we go from...
-
Bounding Linear Programs by Constraint Propagation: Application to Max-SAT
The Virtual Arc Consistency (VAC) algorithm by Cooper et al. is a soft local consistency technique that computes, in linear space, a bound on the...
-
Lower Bounds of Functions on Finite Abelian Groups
The problem of computing the optimum of functions on finite abelian groups is an important problem in mathematics and computer science. Many...
-
On the use of Max-SAT and PDDL in RBAC maintenance
Role-Based Access Control (RBAC) policies are at the core of Cybersecurity as they ease the enforcement of basic security principles, e.g., Least...
-
The Use of Max-Sat for Optimal Choice of Automated Theory Repairs
The ABC system repairs faulty Datalog theories using a combination of abduction, belief revision and conceptual change via reformation. Abduction and...
-
Giving a Model-Based Testing Language a Formal Semantics via Partial MAX-SAT
Domain-specific Languages (DSLs) are widely used in model-based testing to make the benefits of modeling available to test engineers while avoiding...
-
Implementing 3-SAT Gadgets for Quantum Annealers with Random Instances
The Maximum Boolean Satisfiability Problem (also known as the Max-SAT problem) is the problem of determining the maximum number of disjunctive...
-
Multi-user Security of the Sum of Truncated Random Permutations
For several decades, constructing pseudorandom functions from pseudorandom permutations, so-called Luby-Rackoff backward construction, has been a...