An Exact MaxSAT Algorithm: Further Observations and Further Improvements
Authors: Mingyu Xiao
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we further improve the result to O (1.2886m). By using some new reduction and branching techniques we can avoid several bottlenecks in previous algorithms and get the improvement on this important problem. The algorithm will apply the above seven branching steps in order. However, before applying each branching step, we first iteratively apply our reduction rules in order until the instance becomes reduced. We only execute our branching operations on reduced instances. All the reductions can be done in polynomial time. |
| Researcher Affiliation | Academia | Mingyu Xiao University of Electronic Science and Technology of China, Chengdu, China myxiao@uestc.edu.cn |
| Pseudocode | No | The paper describes various reduction rules (R-Rule 1-9) and branching operations (Step 1-7) in detailed textual descriptions and tables, but it does not present any formal pseudocode or algorithm blocks. |
| Open Source Code | No | No statement or link indicates that the authors have released open-source code for the methodology described in this paper. |
| Open Datasets | No | The paper discusses algorithms for the maximum satisfiability problem (Max SAT) on CNF formulas with variables and clauses. It focuses on theoretical running time bounds and does not mention using specific named datasets for experimental evaluation. |
| Dataset Splits | No | The paper focuses on theoretical algorithm improvement and complexity analysis for Max SAT. It does not describe experimental validation dataset splits (e.g., train/validation/test percentages or counts). |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to conduct experiments or derive results. It is a theoretical paper focused on algorithm complexity. |
| Software Dependencies | No | The paper describes an algorithm and its theoretical running time. It does not mention any specific software dependencies or their version numbers required for implementation or reproduction. |
| Experiment Setup | No | The paper focuses on the theoretical development and analysis of an exact Max SAT algorithm and its running time complexity. It does not describe an experimental setup with hyperparameters or system-level training settings. |