Partial minimum satisfiability: fine-grained analysis

DOI10.1613/JAIR.1.19378MaRDI QIDQ7306229zbMATH OpenFDO

Authors I. A. Bliznets, Danil Sagunov, Kirill Simonov

Publication date 30 July 2026

Published in The Journal of Artificial Intelligence Research (JAIR) (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1613/JAIR.1.19378

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites work

• Algorithms and Computation
• An improved upper bound for SAT
• Approximating MIN 2-SAT and MIN 3-SAT
• Differential approximation of MIN SAT, MAX SAT and related problems
• Exact algorithms for maximum independent set
• Exact algorithms via monotone local search
• scientific article; zbMATH DE number 1303594 (Why is no real title available?)
• scientific article; zbMATH DE number 1522934 (Why is no real title available?)
• scientific article; zbMATH DE number 1405665 (Why is no real title available?)
• Improved exact algorithms for MAX-SAT
• Maximal falsifiability. Definitions, algorithms and applications
• On approximation algorithms for the minimum satisfiability problem
• On problems as hard as CNF-SAT
• On reducing maximum independent set to minimum satisfiability
• Optimizing with minimum satisfiability
• Parameterized algorithms
• Solving min ones 2-SAT as fast as vertex cover
• Solving satisfiability in less than \(2^ n\) steps
• The Minimum Satisfiability Problem
• The small set vertex expansion problem

This page was built for publication: Partial minimum satisfiability: fine-grained analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7306229)