scientific article; zbMATH DE number 1775443

zbMATH Open1028.68066MaRDI QIDQ4542575FDOQ4542575

Authors: Uri Zwick 

Publication date: 1 August 2002

Title of this publication is not available (Why is that?)

Recommendations

• Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set
• scientific article; zbMATH DE number 6783493
• \((2+\varepsilon)\)-Sat is NP-hard
• Why almost all satisfiable k-CNF formulas are easy
• Approximating satisfiable satisfiability problems

zbMATH Keywords

constraint satisfaction problemsconjunctive Boolean formulae

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (10)

• Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set
• The complexity of minimal satisfiability problems
• Worst-case study of local search for MAX-\(k\)-SAT.
• Complexity of approximating CSP with balance/hard constraints
• Linear satisfiability preserving assignments
• SDPs and robust satisfiability of promise CSP
• Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
• \((2+\varepsilon)\)-Sat is NP-hard
• Robust algorithms with polynomial loss for near-unanimity CSPs
• Robustly solvable constraint satisfaction problems

This page was built for publication:

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