New Length Dependent Algorithm for Maximum Satisfiability Problem
Abstract
In this paper, we study the computational complexity of the Maximum Satisfiability problem in terms of the length L of a given formula. We present an algorithm with running time O(1.0927^L), hence, improving the previously known best upper bound O(1.1058^L) developed more than 20 years ago by Bansal and Raman. Theoretically speaking, our algorithm increases the length of solvable formulas by 13.3% (compare this to the recent breakthrough result for Maximum Satisfiability problem with respect to the number of clauses by Xu et al. in 2019 giving a 7.5% improvement). Besides, we propose a significantly simpler algorithm with running time O(1.1049^L). The algorithm outperforms Bansal's and Raman's algorithm in simplicity and running time.
Cite
Text
Alferov and Bliznets. "New Length Dependent Algorithm for Maximum Satisfiability Problem." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I5.16479Markdown
[Alferov and Bliznets. "New Length Dependent Algorithm for Maximum Satisfiability Problem." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/alferov2021aaai-new/) doi:10.1609/AAAI.V35I5.16479BibTeX
@inproceedings{alferov2021aaai-new,
title = {{New Length Dependent Algorithm for Maximum Satisfiability Problem}},
author = {Alferov, Vasily and Bliznets, Ivan},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2021},
pages = {3634-3641},
doi = {10.1609/AAAI.V35I5.16479},
url = {https://mlanthology.org/aaai/2021/alferov2021aaai-new/}
}