Improved Algorithms for Maximum Satisfiability and Its Special Cases
Authors: Kirill Brilliantov, Vasily Alferov, Ivan Bliznets
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | For the (n, 3)-MAXSAT problem, we design a O (1.1749n) algorithm improving on the previous record running time of O (1.191n). For the (n, 4)-MAXSAT problem, we construct a O (1.3803n) algorithm improving on the previous best running time of O (1.4254n). Using the results, we develop a O (1.0911L) algorithm for the MAXSAT where L is a length of the input formula which improves previous algorithm with O (1.0927L) running time. |
| Researcher Affiliation | Academia | Kirill Brilliantov1, Vasily Alferov2, Ivan Bliznets3 1 Constructor University 2 Independent Researcher 3 Utrecht University ki.br178@gmail.com, vasily.v.alferov@gmail.com, iabliznets@gmail.com/i.bliznets@uu.nl |
| Pseudocode | No | The paper describes reduction rules and branching rules, but it does not present them in structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information for source code or state that it is open-source. |
| Open Datasets | No | This theoretical paper focuses on algorithm design and complexity analysis for MAXSAT problems, and as such, it does not use specific datasets or provide access information for them. |
| Dataset Splits | No | This theoretical paper does not discuss or provide specific dataset split information for training, validation, or testing. |
| Hardware Specification | No | The paper does not provide specific hardware details used for running any experiments, consistent with its theoretical nature. |
| Software Dependencies | No | The paper does not provide specific ancillary software details, such as library or solver names with version numbers. |
| Experiment Setup | No | The paper does not contain specific experimental setup details such as hyperparameter values, training configurations, or system-level settings. |