A Fast Algorithm for MaxSAT above Half Number of Clauses
Authors: Junqiang Peng, Mingyu Xiao
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Junqiang Peng , Mingyu Xiao University of Electronic Science and Technology of China, Chengdu, China jqpeng0@foxmail.com, myxiao@uestc.edu.cn |
| Pseudocode | No | The paper describes various reduction and branching rules in textual form and through lemmas, but it does not present a unified pseudocode block or algorithm figure. |
| Open Source Code | No | The paper does not mention providing any open-source code for the methodology described. |
| Open Datasets | No | The paper describes a theoretical algorithm and its complexity analysis. There are no empirical experiments involving datasets or training. |
| Dataset Splits | No | The paper describes a theoretical algorithm and its complexity analysis. There are no empirical experiments involving dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper describes a theoretical algorithm and its complexity. There are no empirical experiments mentioned that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical, presenting an algorithm and its complexity analysis. It does not mention any specific software dependencies with version numbers required for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical, presenting an algorithm and its complexity analysis. It does not describe any empirical experiment setup details such as hyperparameters or system-level training settings. |