IJCAI 2024poster0 citations
A Fast Algorithm for MaxSAT above Half Number of Clauses
Abstract
We study the following parameterization of the MaxSAT problem: Given a CNF formula F with m clauses, decide whether at least m/2 + μ clauses in F could be satisfied, where μ is the excess of the number of satisfied clauses over the trivial lower bound m/2 and is taken as the parameter. This perspective is known as the "above guarantee" parameterization. Since its introduction by Mahajan and Raman [1999], the analysis of parameterization above guarantee has become a highly active and fruitful line of research. In this paper, we develop a new algorithm with runtime O*(2.1479^μ), significantly improving the previous best upper bound O*(5.4064^μ) for this important problem. Here, the O* notation omits polynomial factors.
Constraint Satisfaction and Optimization: CSO: SatisfiabiltyConstraint Satisfaction and Optimization: CSO: Constraint optimization problemsConstraint Satisfaction and Optimization: CSO: Constraint satisfactionSearch: S: Combinatorial search and optimisation
BibTeX
@inproceedings{ijcai2024p214,
title = {A Fast Algorithm for MaxSAT above Half Number of Clauses},
author = {Peng, Junqiang and Xiao, Mingyu},
booktitle = {Proceedings of the Thirty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-24}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Kate Larson},
pages = {1935--1943},
year = {2024},
month = {8},
note = {Main Track},
doi = {10.24963/ijcai.2024/214},
url = {https://doi.org/10.24963/ijcai.2024/214},
}