ML Anthology

Study of Lower Bound Functions for MAX-2-SAT

Haiou Shen, Hantao Zhang
AAAI 2004 pp. 185-190
/aaai/2004/shen2004aaai-study/

Abstract

Recently, several lower bound functions are proposed for solving the MAX-2-SAT problem optimally in a branch-and-bound algorithm. These lower bounds improve significantly the performance of these algorithms. Based on the study of these lower bound functions, we propose a new, linear-time lower bound function. We show that the new lower bound function is admissible and it is consistently and substantially better than other known lower bound functions. The result of this study is a high-performance implementation of an exact algorithm for MAX-2-SAT which outperforms any implementation of the same class.

PDF AAAI Semantic Scholar

Cite

Text

Shen and Zhang. "Study of Lower Bound Functions for MAX-2-SAT." AAAI Conference on Artificial Intelligence, 2004.

Markdown

[Shen and Zhang. "Study of Lower Bound Functions for MAX-2-SAT." AAAI Conference on Artificial Intelligence, 2004.](https://mlanthology.org/aaai/2004/shen2004aaai-study/)

BibTeX

@inproceedings{shen2004aaai-study,
  title     = {{Study of Lower Bound Functions for MAX-2-SAT}},
  author    = {Shen, Haiou and Zhang, Hantao},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2004},
  pages     = {185-190},
  url       = {https://mlanthology.org/aaai/2004/shen2004aaai-study/}
}