Approximating satisfiable satisfiability problems (extended abstract)

DOI10.1007/3-540-63397-9_36MaRDI QIDQ826119zbMATH OpenOpenAlexFDO

Authors Luca Trevisan

Publication date 20 December 2021

Full work available at URL https://doi.org/10.1007/3-540-63397-9_36

zbMATH Keywords

approximation algorithmconstraint satisfaction problemsatisfiability problemsatisfying assignmentunit clause

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Computational aspects of satisfiability (68R07)

Recommendations

• Approximating satisfiable satisfiability problems
• Conditional Hardness of Approximating Satisfiable Max 3CSP-q
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Conditional hardness for satisfiable 3-CSPs
• scientific article; zbMATH DE number 1303558

Cited in

(11)

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximating Succinct MaxSat
• On approximability of satisfiable k -CSPs: I
• On the Approximability of Splitting-SAT in 2-CNF Horn Formulas
• scientific article; zbMATH DE number 6783493 (Why is no real title available?)
• Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
• Sparsification of SAT and CSP Problems via Tractable Extensions
• Efficient Approximation of Well-Founded Justification and Well-Founded Domination
• An approximative inference method for solving ∃∀SO satisfiability problems

This page was built for publication: Approximating satisfiable satisfiability problems (extended abstract)

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