Resolution and Domination: An Improved Exact MaxSAT Algorithm
Authors: Chao Xu, Wenjun Li, Yongjie Yang, Jianer Chen, Jianxin Wang
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the MAXIMUM SATISFIABILITY problem (MAXSAT). Particularly, we derive a branching algorithm of running time O (1.2989m) 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.3248m) by Chen and Kanj [2004] published 15 years ago. |
| Researcher Affiliation | Academia | 1School of Computer Science and Engineering, Central South University, Changsha, China 2School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha, China 3Chair of Economic Theory, Saarland University, Saarbr ucken, Germany 4Department of Computer Science and Engineering, Texas A&M University, College Station, USA |
| Pseudocode | No | The paper describes algorithms verbally and through lemmas but does not include any clearly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any statement about releasing source code or links to a code repository. |
| Open Datasets | No | This is a theoretical paper focusing on algorithm design and analysis, not empirical evaluation on datasets. Therefore, it does not use or mention any specific dataset for training. |
| Dataset Splits | No | This is a theoretical paper focusing on algorithm design and analysis. It does not involve dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper on algorithm complexity analysis and does not describe any computational experiments or the hardware used to run them. |
| Software Dependencies | No | This is a theoretical paper; it does not mention any specific software or programming languages with version numbers that would be required to replicate experimental results. |
| Experiment Setup | No | This is a theoretical paper focused on algorithm design and analysis; it does not include details on experimental setup such as hyperparameters or training configurations. |