Algorithms for the maximum satisfiability problem
From MaRDI portal
DOI10.1007/BF02241270zbMATH Open0716.68077MaRDI QIDQ753502FDOQ753502
Authors: Pierre Hansen, Brigitte Jaumard 
Publication date: 1990
Published in: Computing (Search for Journal in Brave)
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
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)
Cites Work
- Optimization by simulated annealing
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- Future paths for integer programming and links to artificial intelligence
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- The complexity of satisfiability problems
- The complexity of theorem-proving procedures
- A simplified NP-complete satisfiability problem
- Some simplified NP-complete graph problems
- On the Complexity of Timetable and Multicommodity Flow Problems
- Title not available (Why is that?)
- Some Extremal Properties of Bipartite Subgraphs
- A Computing Procedure for Quantification Theory
- Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
- Complete problems for deterministic polynomial time
- On the complexity of the maximum satisfiability problem for Horn formulas
- Some results and experiments in programming techniques for propositional logic
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities
- The tabu search metaheuristic: How we used it
- A thermodynamically motivated simulation procedure for combinatorial optimization problems
- Methods of Nonlinear 0-1 Programming
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Complexity of Partial Satisfaction
- Unit Refutations and Horn Sets
- Input Proofs and Rank One Cutting Planes
- Algorithmic extremal problems in combinatorial optimization
- Title not available (Why is that?)
- Simulated annealing methods with general acceptance probabilities
- An \(O(n^ 2)\) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences
- The satisfiabilty problem for a class consisting of horn sentences and some non-horn sentences in proportional logic
- A cascade algorithm for the logical closure of a set of binary relations
- Integrity constraints in logic databases
Cited In (79)
- An analysis of parameter adaptation in reactive tabu search
- Title not available (Why is that?)
- Probably partially true: satisfiability for Łukasiewicz infinitely-valued probabilistic logic and related topics
- Revisiting simulated annealing: a component-based analysis
- Rank-constrained fundamental matrix estimation by polynomial global optimization versus the eight-point algorithm
- Title not available (Why is that?)
- Near-optimal algorithms for maximum constraint satisfaction problems
- Heuristic reliability optimization by tabu search
- An artificial neural network satisfiability tester
- Discrete dynamical system approaches for Boolean polynomial optimization
- A Theoretical Analysis of Search in GSAT
- On optimization problems in acyclic hypergraphs
- Formal methods for reasoning and uncertainty reduction in evidential grid maps
- An inventory-routing problem with the objective of travel time minimization
- Constraint learning: an appetizer
- 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
- A user's guide to tabu search
- Efficient branch-and-bound algorithms for weighted MAX-2-SAT
- MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\)
- 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
- Worst-case study of local search for MAX-\(k\)-SAT.
- Variable neighborhood search: Principles and applications
- A tabu search procedure for multicommodity location/allocation with balancing requirements
- Improving exact algorithms for MAX-2-SAT
- Boolean query optimization and the 0-1 hyperbolic sum problem
- Solving thep-Center problem with Tabu Search and Variable Neighborhood Search
- Probabilistic bounds and algorithms for the maximum satisfiability problem
- A tabu search Hooke and Jeeves algorithm for unconstrained optimization
- Minimization of a quadratic pseudo-Boolean function
- A finite state intersection approach to propositional satisfiability
- Variable neighborhood search
- Algorithms for four variants of the exact satisfiability problem
- Best second order bounds for two-terminal network reliability with dependent edge failures
- Finding a feasible course schedule using Tabu search
- Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem
- Title not available (Why is that?)
- Probabilistic estimates for the generalized maximum satisfiability problem
- 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
- Exact algorithms for MAX-SAT
- On the greedy algorithm for satisfiability
- Deconstructing Nowicki and Smutnicki's \(i\)-TSAB tabu search algorithm for the job-shop scheduling problem
- 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 and clause ordering in an FSA approach to propositional satisfiability
- Variable neighborhood search for the maximum clique
- A tabu search algorithm for computing an operational timetable
- Solving weighted MAX-SAT via global equilibrium search
- 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
- An Empirical Study of MAX-2-SAT Phase Transitions
- An efficient solver for weighted Max-SAT
- Experimental and Efficient Algorithms
- Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?
- EPCOT: An efficient procedure for coloring optimally with Tabu Search
- Location and sizing of offshore platforms for oil exploration
- Algorithmic approach to the satisfactory graph partitioning problem
- 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
- Analysis and solving SAT and MAX-SAT problems using an \(L\)-partition approach
- Solving the maximum clique problem using a tabu search approach
- Metaheuristics: A bibliography
- \textsc{ahmaxsat}: description and evaluation of a branch and bound Max-SAT solver
- Genetic algorithms and tabu search: Hybrids for optimization
- Improved exact algorithms for MAX-SAT
- New local search approximation techniques for maximum generalized satisfiability problems
- Compiling propositional weighted bases
- Algorithms for Solving Satisfiability Problems with Qualitative Preferences
- Hashing vectors for tabu search
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)
