Approximating Succinct MaxSat

DOI10.1093/LOGCOM/EXI033MaRDI QIDQ5696308zbMATH OpenOpenAlexFDO

Authors Christian Schallhart, Luca Trevisan

Publication date 18 October 2005

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/exi033

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Recommendations

• Approximating satisfiable satisfiability problems
• scientific article; zbMATH DE number 1445292
• Approximating satisfiable satisfiability problems (extended abstract)
• MAX3SAT is exponentially hard to approximate if NP has positive dimension.
• Approximation and Online Algorithms

Cited in

(3)

• Approximating a generalization of MAX 2SAT and MIN 2SAT
• MAX3SAT is exponentially hard to approximate if NP has positive dimension.
• Query-guided maximum satisfiability

This page was built for publication: Approximating Succinct MaxSat

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