scientific article; zbMATH DE number 1775443

MaRDI QIDQ4542575zbMATH OpenFDO

Authors Uri Zwick

Publication date 1 August 2002

zbMATH Keywords

conjunctive Boolean formulaeconstraint satisfaction problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

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

Cited in

(11)

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

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)