{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:30:54Z","timestamp":1723015854829},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,8]]},"abstract":"<jats:p>We study the Maximum Satisfiability problem (MaxSAT). Particularly, we derive a branching algorithm of running time O*(1.2989^m) for the MaxSAT problem,  where m denotes the number of clauses in the given CNF formula. Our algorithm considerably improves the previous best result O*(1.3248^m) by Chen and Kanj [2004] published 15 years ago. For our purpose, we derive improved branching strategies for variables of degrees 3, 4, and 5. The worst case of our branching algorithm is at variables of degree 4 which occur twice both positively and negatively in the given CNF formula. To serve the branching rules and shrink the size of the CNF formula, we also propose a variety of reduction rules which can be exhaustively applied in polynomial time and, moreover, some of them solve a bottleneck of the previous best algorithm.<\/jats:p>","DOI":"10.24963\/ijcai.2019\/166","type":"proceedings-article","created":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T07:46:05Z","timestamp":1564299965000},"page":"1191-1197","source":"Crossref","is-referenced-by-count":3,"title":["Resolution and Domination: An Improved Exact MaxSAT Algorithm"],"prefix":"10.24963","author":[{"given":"Chao","family":"Xu","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Central South University, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenjun","family":"Li","sequence":"additional","affiliation":[{"name":"School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongjie","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Central South University, Changsha, China"},{"name":"Chair of Economic Theory, Saarland University, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianer","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Texas A&M University, College Station, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Central South University, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2019","name":"Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}","start":{"date-parts":[[2019,8,10]]},"theme":"Artificial Intelligence","location":"Macao, China","end":{"date-parts":[[2019,8,16]]}},"container-title":["Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T07:47:16Z","timestamp":1564300036000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2019\/166"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2019\/166","relation":{},"subject":[],"published":{"date-parts":[[2019,8]]}}}