On the lower bounds of random Max 3 and 4-SAT.
Guangyan ZhouZongsheng GaoPublished in: J. Comb. Optim. (2018)
Keyphrases
- lower bound
- max sat
- upper bound
- np hard
- random instances
- branch and bound
- objective function
- branch and bound algorithm
- sat solvers
- lower and upper bounds
- search algorithm
- worst case
- sat problem
- optimal solution
- quadratic assignment problem
- stochastic local search
- orders of magnitude
- upper and lower bounds
- vc dimension
- linear programming relaxation
- satisfiability problem
- variable ordering
- randomly generated
- phase transition
- propositional satisfiability
- optimal cost