Research map / Learning theory and algorithms / Combinatorial and search optimization
Improved Algorithms for Maximum Satisfiability and Its Special Cases
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the improved branching and reduction rules for (n, 3)-MAXSAT | (n, 3)-MAXSAT · (n, 3)-MAXSAT | running time: O∗(1.191n) -> O∗(1.1749n) | Helped |
| Use the improved branching and reduction rules for (n, 4)-MAXSAT | (n, 4)-MAXSAT · (n, 4)-MAXSAT | running time: O∗(1.4254n) -> O∗(1.3803n) | Helped |
| Use the improved bounded-occurrence algorithms to solve general MAXSAT | MAXSAT · MAXSAT | running time: O∗(1.0927L) -> O∗(1.0911L) | Helped |
| Use the algorithm in terms of k for (n, 3)-MAXSAT | (n, 3)-MAXSAT · (n, 3)-MAXSAT | running time: O∗(1.1554k) | Helped |
| Use the algorithm in terms of k for (n, 4)-MAXSAT | (n, 4)-MAXSAT · (n, 4)-MAXSAT | running time: O∗(1.2989k) | Helped |
| Use the discounted-length measure instead of measuring complexity only by formula length | The MAXSAT algorithm · MAXSAT | running time: O∗(1.08391d), O∗(1.08391L), O∗(1.0911d), O∗(1.0911L) | Helped |
Closest papers by meaning
- Ordered Objectives in Maximum Satisfiability (AAAI 2026 · similarity 0.93)
- Improving the Lower Bound in Branch-and-Bound Algorithms for MaxSAT (AAAI 2025 · similarity 0.92)
- Parameterization of (Partial) Maximum Satisfiability above Matching in a Variable-Clause Graph (AAAI 2024 · similarity 0.92)
- New Length Dependent Algorithm for Maximum Satisfiability Problem (AAAI 2021 · similarity 0.91)
- Enhance Diversified Top-k MaxSAT Solving by Incorporating New Strategy for Generating Diversified Initial Assignments (Student Abstract) (AAAI 2024 · similarity 0.87)
- DiverSAT: A Novel and Effective Local Search Algorithm for Diverse SAT Problem (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.