Algorithms for the maximum satisfiability problem
From MaRDI portal
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Parallel algorithms in computer science (68W10) Complexity of computation (including implicit computational complexity) (03D15)
Recommendations
- Approximation algorithms for the maximum satisfiability problem
- scientific article; zbMATH DE number 1302170
- Probabilistic bounds and algorithms for the maximum satisfiability problem
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- scientific article; zbMATH DE number 956866
Cites work
- scientific article; zbMATH DE number 3874667 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3249560 (Why is no real title available?)
- A Computing Procedure for Quantification Theory
- A cascade algorithm for the logical closure of a set of binary relations
- A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- A simplified NP-complete satisfiability problem
- A thermodynamically motivated simulation procedure for combinatorial optimization problems
- Algorithmic extremal problems in combinatorial optimization
- An \(O(n^ 2)\) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences
- Approximation algorithms for combinatorial problems
- Complete problems for deterministic polynomial time
- Complexity of Partial Satisfaction
- Future paths for integer programming and links to artificial intelligence
- Input Proofs and Rank One Cutting Planes
- Integrity constraints in logic databases
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Methods of Nonlinear 0-1 Programming
- On the Complexity of Timetable and Multicommodity Flow Problems
- On the complexity of the maximum satisfiability problem for Horn formulas
- Optimization by simulated annealing
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- Simulated annealing methods with general acceptance probabilities
- Some Extremal Properties of Bipartite Subgraphs
- Some results and experiments in programming techniques for propositional logic
- Some simplified NP-complete graph problems
- The complexity of satisfiability problems
- The complexity of theorem-proving procedures
- The satisfiabilty problem for a class consisting of horn sentences and some non-horn sentences in proportional logic
- The tabu search metaheuristic: How we used it
- Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
- Unit Refutations and Horn Sets
Cited in
(79)- Scatter search and genetic algorithms for MAX-SAT problems
- Modelling the dynamics of stochastic local search on \(k\)-SAT
- An algorithm based on tabu search for satisfiability problem
- Worst-case study of local search for MAX-\(k\)-SAT.
- MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
- Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?
- Improving exact algorithms for MAX-2-SAT
- EPCOT: An efficient procedure for coloring optimally with Tabu Search
- The unconstrained binary quadratic programming problem: a survey
- Improved exact algorithms for MAX-SAT
- An Empirical Study of MAX-2-SAT Phase Transitions
- Solving the maximum clique problem using a tabu search approach
- An efficient solver for weighted Max-SAT
- Tight bound on Johnson's algorithm for maximum satisfiability
- Best second order bounds for two-terminal network reliability with dependent edge failures
- Boolean query optimization and the 0-1 hyperbolic sum problem
- A tabu search Hooke and Jeeves algorithm for unconstrained optimization
- Boolean regression
- Variable and clause ordering in an FSA approach to propositional satisfiability
- Metaheuristics: A bibliography
- Boolean lexicographic optimization: algorithms \& applications
- Probabilistic satisfiability: algorithms with the presence and absence of a phase transition
- Finding a feasible course schedule using Tabu search
- Global optimization for artificial neural networks: A tabu search application
- New local search approximation techniques for maximum generalized satisfiability problems
- Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\)
- A finite state intersection approach to propositional satisfiability
- Compiling propositional weighted bases
- New approaches for heuristic search: A bilateral linkage with artificial intelligence
- Analysis and solving SAT and MAX-SAT problems using an \(L\)-partition approach
- Variable neighborhood search for the maximum clique
- A fixed point operator for the generalised maximum satisfiability problem
- Variable neighborhood search
- Exact algorithms for MAX-SAT
- A tabu search algorithm for computing an operational timetable
- Deconstructing Nowicki and Smutnicki's \(i\)-TSAB tabu search algorithm for the job-shop scheduling problem
- Solving thep-Center problem with Tabu Search and Variable Neighborhood Search
- Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem
- Algorithms for Solving Satisfiability Problems with Qualitative Preferences
- Minimization of a quadratic pseudo-Boolean function
- Hashing vectors for tabu search
- Solving weighted MAX-SAT via global equilibrium search
- A user's guide to tabu search
- Strategies with memories: Local search in an application oriented environment. Applied local search -- a prologue
- scientific article; zbMATH DE number 6381632 (Why is no real title available?)
- Location and sizing of offshore platforms for oil exploration
- A theoretical analysis of the cross-nested logit model
- The tabu search metaheuristic: How we used it
- TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
- A comparison of neighborhood search techniques for multi-objective combinatorial problems
- \textsc{ahmaxsat}: description and evaluation of a branch and bound Max-SAT solver
- A tabu search procedure for multicommodity location/allocation with balancing requirements
- Probabilistic bounds and algorithms for the maximum satisfiability problem
- Algorithmic approach to the satisfactory graph partitioning problem
- Experimental and Efficient Algorithms
- Variable neighborhood search: Principles and applications
- Probabilistic estimates for the generalized maximum satisfiability problem
- On the greedy algorithm for satisfiability
- Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems
- Efficient branch-and-bound algorithms for weighted MAX-2-SAT
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- Resolution and the integrality of satisfiability problems
- Genetic algorithms and tabu search: Hybrids for optimization
- Algorithms for four variants of the exact satisfiability problem
- On optimization problems in acyclic hypergraphs
- Discrete dynamical system approaches for Boolean polynomial optimization
- scientific article; zbMATH DE number 7310195 (Why is no real title available?)
- Revisiting simulated annealing: a component-based analysis
- Heuristic reliability optimization by tabu search
- Near-optimal algorithms for maximum constraint satisfaction problems
- Probably partially true: satisfiability for Łukasiewicz infinitely-valued probabilistic logic and related topics
- An analysis of parameter adaptation in reactive tabu search
- An artificial neural network satisfiability tester
- Constraint learning: an appetizer
- scientific article; zbMATH DE number 1182571 (Why is no real title available?)
- A Theoretical Analysis of Search in GSAT
- Rank-constrained fundamental matrix estimation by polynomial global optimization versus the eight-point algorithm
- An inventory-routing problem with the objective of travel time minimization
- Formal methods for reasoning and uncertainty reduction in evidential grid maps
This page was built for publication: Algorithms for the maximum satisfiability problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q753502)
