Approximating Max NAE-k-SAT by anonymous local search

DOI10.1016/J.TCS.2016.05.040MaRDI QIDQ507440zbMATH OpenOpenAlexFDO

Authors Aiyong Xian, Kaiyuan Zhu, Daming Zhu, Lianrong Pu, Hong Liu

Publication date 6 February 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.05.040

zbMATH Keywords

algorithmcomplexitylocal searchperformance ratiosatisfiability

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Local search to approximate MAX NAE-\(k\)-SAT tightly
• Approximation and Online Algorithms
• Tight bounds on local search to approximate the maximum satisfiability problems
• Worst-case study of local search for MAX-\(k\)-SAT.
• New local search approximation techniques for maximum generalized satisfiability problems

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• An algorithm based on tabu search for satisfiability problem
• Approximation algorithms for combinatorial problems
• Approximation and Online Algorithms
• Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
• Improved approximation algorithms for MAX SAT
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improved approximations for max set splitting and max NAE SAT
• Local search characteristics of incomplete SAT procedures
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• On Syntactic versus Computational Views of Approximability
• On the Approximation of Maximum Satisfiability
• Optimization, approximation, and complexity classes
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
• The complexity of theorem-proving procedures
• Tight bound on Johnson's algorithm for maximum satisfiability
• Tight bounds on local search to approximate the maximum satisfiability problems

Cited in

(3)

• Tight bounds on local search to approximate the maximum satisfiability problems
• On the mysteries of MAX NAE-SAT
• Local search to approximate MAX NAE-\(k\)-SAT tightly

Describes a project that uses

Uses Software

• Outward rotations

This page was built for publication: Approximating Max NAE-\(k\)-SAT by anonymous local search

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