Probabilistic bounds and algorithms for the maximum satisfiability problem
From MaRDI portal
Publication:920845
DOI10.1007/BF02022095zbMath0708.90058MaRDI QIDQ920845
Publication date: 1989
Published in: Annals of Operations Research (Search for Journal in Brave)
Linear programming (90C05) Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
New bounds for the probability that at least \(k\)-out-of-\(n\) events occur with unimodal distributions, On the relationship between the discrete and continuous bounding moment problems and their numerical solutions, Building an iterative heuristic solver for a quantum annealer, Maximum renamable Horn sub-CNFs, Pseudo-Boolean optimization, Improved bounds on the probability of the union of events some of whose intersections are empty, Bounds for the probability of union of events following monotonic distribution, Sharp bounds for the probability of union of \(n\) events when \(m\) number of binomial moments are known, Covering non-uniform hypergraphs, The value of shape constraints in discrete moment problems: a review and extension, An unconstrained quadratic binary programming approach to the vertex coloring problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms for the maximum satisfiability problem
- Average time analyses of simplified Davis-Putnam procedures
- A thermodynamically motivated simulation procedure for combinatorial optimization problems
- On the complexity of the maximum satisfiability problem for Horn formulas
- Resolution vs. cutting plane solution of inference problems: Some computational experience
- Some results and experiments in programming techniques for propositional logic
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- Approximation algorithms for combinatorial problems
- Some simplified NP-complete graph problems
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Many hard examples for resolution
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- Roof duality for polynomial 0–1 optimization
- Boole-Bonferroni Inequalities and Linear Programming
- Complexity of Partial Satisfaction
- Algorithmic extremal problems in combinatorial optimization
- On the Complexity of Timetable and Multicommodity Flow Problems
- A Computing Procedure for Quantification Theory
- The complexity of theorem-proving procedures
