IJCAI 2022poster11 citations
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.
Constraint Satisfaction and Optimization: Satisfiabilty
BibTeX
@inproceedings{ijcai2022p262,
title = {An Exact MaxSAT Algorithm: Further Observations and Further Improvements},
author = {Xiao, Mingyu},
booktitle = {Proceedings of the Thirty-First International Joint Conference on
Artificial Intelligence, {IJCAI-22}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Lud De Raedt},
pages = {1887--1893},
year = {2022},
month = {7},
note = {Main Track},
doi = {10.24963/ijcai.2022/262},
url = {https://doi.org/10.24963/ijcai.2022/262},
}