Algorithms for the maximum satisfiability problem
From MaRDI portal
(Redirected from Publication:753502)
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)- A theoretical analysis of the cross-nested logit model
- Tight bound on Johnson's algorithm for maximum satisfiability
- A fixed point operator for the generalised maximum satisfiability problem
- Efficient branch-and-bound algorithms for weighted MAX-2-SAT
- A user's guide to tabu search
- MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
- An analysis of parameter adaptation in reactive tabu search
- scientific article; zbMATH DE number 1182571 (Why is no real title available?)
- Reactive local search techniques for the maximum k-conjunctive constraint satisfaction problem (MAX-k-CCSP)
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- Resolution and the integrality of satisfiability problems
- New approaches for heuristic search: A bilateral linkage with artificial intelligence
- The unconstrained binary quadratic programming problem: a survey
- Boolean lexicographic optimization: algorithms \& applications
- Boolean regression
- Probably partially true: satisfiability for Łukasiewicz infinitely-valued probabilistic logic and related topics
- Worst-case study of local search for MAX-\(k\)-SAT.
- Revisiting simulated annealing: a component-based analysis
- Improving exact algorithms for MAX-2-SAT
- A tabu search procedure for multicommodity location/allocation with balancing requirements
- Boolean query optimization and the 0-1 hyperbolic sum problem
- Variable neighborhood search: Principles and applications
- Probabilistic bounds and algorithms for the maximum satisfiability problem
- Solving thep-Center problem with Tabu Search and Variable Neighborhood Search
- A tabu search Hooke and Jeeves algorithm for unconstrained optimization
- Minimization of a quadratic pseudo-Boolean function
- Rank-constrained fundamental matrix estimation by polynomial global optimization versus the eight-point algorithm
- A finite state intersection approach to propositional satisfiability
- Variable neighborhood search
- Algorithms for four variants of the exact satisfiability problem
- Finding a feasible course schedule using Tabu search
- Best second order bounds for two-terminal network reliability with dependent edge failures
- Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem
- Probabilistic estimates for the generalized maximum satisfiability problem
- scientific article; zbMATH DE number 6381632 (Why is no real title available?)
- Strategies with memories: Local search in an application oriented environment. Applied local search -- a prologue
- A comparison of neighborhood search techniques for multi-objective combinatorial problems
- On the greedy algorithm for satisfiability
- Near-optimal algorithms for maximum constraint satisfaction problems
- scientific article; zbMATH DE number 7310195 (Why is no real title available?)
- Exact algorithms for MAX-SAT
- Heuristic reliability optimization by tabu search
- Deconstructing Nowicki and Smutnicki's \(i\)-TSAB tabu search algorithm for the job-shop scheduling problem
- An artificial neural network satisfiability tester
- Discrete dynamical system approaches for Boolean polynomial optimization
- Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems
- Probabilistic satisfiability: algorithms with the presence and absence of a phase transition
- An algorithm based on tabu search for satisfiability problem
- Variable neighborhood search for the maximum clique
- A tabu search algorithm for computing an operational timetable
- Solving weighted MAX-SAT via global equilibrium search
- TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
- The tabu search metaheuristic: How we used it
- Variable and clause ordering in an FSA approach to propositional satisfiability
- A Theoretical Analysis of Search in GSAT
- An Empirical Study of MAX-2-SAT Phase Transitions
- An efficient solver for weighted Max-SAT
- Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?
- EPCOT: An efficient procedure for coloring optimally with Tabu Search
- Experimental and Efficient Algorithms
- Location and sizing of offshore platforms for oil exploration
- Algorithmic approach to the satisfactory graph partitioning problem
- On optimization problems in acyclic hypergraphs
- Global optimization for artificial neural networks: A tabu search application
- Scatter search and genetic algorithms for MAX-SAT problems
- Modelling the dynamics of stochastic local search on \(k\)-SAT
- Formal methods for reasoning and uncertainty reduction in evidential grid maps
- Analysis and solving SAT and MAX-SAT problems using an L-partition approach
- Metaheuristics: A bibliography
- Solving the maximum clique problem using a tabu search approach
- Genetic algorithms and tabu search: Hybrids for optimization
- An inventory-routing problem with the objective of travel time minimization
- \textsc{ahmaxsat}: description and evaluation of a branch and bound Max-SAT solver
- Improved exact algorithms for MAX-SAT
- New local search approximation techniques for maximum generalized satisfiability problems
- Constraint learning: an appetizer
- Compiling propositional weighted bases
- Hashing vectors for tabu search
- Algorithms for Solving Satisfiability Problems with Qualitative Preferences
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)
