Approximating MIN 2-SAT and MIN 3-SAT
From MaRDI portal
Publication:1780843
DOI10.1007/s00224-005-1140-7zbMath1101.68603OpenAlexW2016001296MaRDI QIDQ1780843
Publication date: 14 June 2005
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-005-1140-7
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (11)
On residual approximation in solution extension problems ⋮ Lower and Upper Bounds for Random Mimimum Satisfiability Problem ⋮ From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ A primal-dual approximation algorithm for \textsc{minsat} ⋮ Minimal sets on propositional formulae. Problems and reductions ⋮ On Residual Approximation in Solution Extension Problems ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ On the Minimum Hitting Set of Bundles Problem ⋮ Optimizing with minimum satisfiability ⋮ Exclusive graph searching vs. pathwidth ⋮ On the minimum hitting set of bundles problem
This page was built for publication: Approximating MIN 2-SAT and MIN 3-SAT
