An Exact MaxSAT Algorithm: Further Observations and Further Improvements
Abstract
In the maximum satisfiability problem (MaxSAT), given a CNF formula with m clauses and n variables, we are asked to find an assignment of the variables to satisfy the maximum number of clauses. Chen and Kanj showed that this problem can be solved in O*(1.3248^m) time (DAM 2004) and the running time bound was improved to O*(1.2989^m) by Xu et al. (IJCAI 2019). In this paper, we further improve the result to O*(1.2886^m). By using some new reduction and branching techniques we can avoid several bottlenecks in previous algorithms and get the improvement on this important problem.
Cite
Text
Xiao. "An Exact MaxSAT Algorithm: Further Observations and Further Improvements." International Joint Conference on Artificial Intelligence, 2022. doi:10.24963/IJCAI.2022/262Markdown
[Xiao. "An Exact MaxSAT Algorithm: Further Observations and Further Improvements." International Joint Conference on Artificial Intelligence, 2022.](https://mlanthology.org/ijcai/2022/xiao2022ijcai-exact/) doi:10.24963/IJCAI.2022/262BibTeX
@inproceedings{xiao2022ijcai-exact,
title = {{An Exact MaxSAT Algorithm: Further Observations and Further Improvements}},
author = {Xiao, Mingyu},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2022},
pages = {1887-1893},
doi = {10.24963/IJCAI.2022/262},
url = {https://mlanthology.org/ijcai/2022/xiao2022ijcai-exact/}
}