Improved approximation algorithms for MAX SAT

DOI10.1006/JAGM.2001.1202MaRDI QIDQ2777611zbMATH OpenOpenAlexFDO

Authors T. Asano, David P. Williamson

Publication date 14 August 2002

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.2001.1202

zbMATH Keywords

maximum satisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1445292
• Approximation algorithms for the maximum satisfiability problem
• Approximation and Online Algorithms
• scientific article; zbMATH DE number 1002206
• An approximation algorithm for MAX 3-SAT

Cited in

(38)

• The labeled perfect matching in bipartite graphs
• Tight bound on Johnson's algorithm for maximum satisfiability
• Simple approximation algorithms for balanced MAX~2SAT
• Approximating MIN 2-SAT and MIN 3-SAT
• Improved approximations for max set splitting and max NAE SAT
• An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT
• Adding cardinality constraints to integer programs with applications to maximum satisfiability
• Improved approximation algorithms for the Min-Max selecting items problem
• scientific article; zbMATH DE number 1629855 (Why is no real title available?)
• Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
• Bounds on greedy algorithms for MAX SAT
• scientific article; zbMATH DE number 1002206 (Why is no real title available?)
• Local search to approximate MAX NAE-k-SAT tightly
• Improvements to Hybrid Incremental SAT Algorithms
• scientific article; zbMATH DE number 1258327 (Why is no real title available?)
• scientific article; zbMATH DE number 1263278 (Why is no real title available?)
• scientific article; zbMATH DE number 1302170 (Why is no real title available?)
• Approximation algorithms for the maximum satisfiability problem
• On Approximation Algorithms for Hierarchical MAX-SAT
• scientific article; zbMATH DE number 1182773 (Why is no real title available?)
• scientific article; zbMATH DE number 1979498 (Why is no real title available?)
• scientific article; zbMATH DE number 1979522 (Why is no real title available?)
• scientific article; zbMATH DE number 1552232 (Why is no real title available?)
• Hinge-loss Markov random fields and probabilistic soft logic
• scientific article; zbMATH DE number 1372698 (Why is no real title available?)
• scientific article; zbMATH DE number 1445292 (Why is no real title available?)
• Approximating Max NAE-\(k\)-SAT by anonymous local search
• Dealing with 4-variables by resolution: an improved MaxSAT algorithm
• On Some Recent Approximation Algorithms for MAX SAT
• Approximation and Online Algorithms
• An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT.
• MAX SAT approximation beyond the limits of polynomial-time approximation
• Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles
• An approximation algorithm for MAX 3-SAT
• On the mysteries of MAX NAE-SAT
• Fault tolerant max-cut
• Separating \textsc{max} 2-and, \textsc{max di-cut}, and \textsc{max cut}
• Sums of squares based approximation algorithms for MAX-SAT

This page was built for publication: Improved approximation algorithms for MAX SAT

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