Approximating Max NAE-\(k\)-SAT by anonymous local search

DOI10.1016/j.tcs.2016.05.040zbMath1356.68210OpenAlexW2415155455MaRDI QIDQ507440

Daming Zhu, Aiyong Xian, Kaiyuan 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

complexityalgorithmlocal searchsatisfiabilityperformance ratio

Mathematics Subject Classification ID

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

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• Tight bound on Johnson's algorithm for maximum satisfiability
• An algorithm based on tabu search for satisfiability problem
• Improved approximations for max set splitting and max NAE SAT
• Improved Approximation Algorithms for MAX SAT
• Outward rotations
• Tight Bounds on Local Search to Approximate the Maximum Satisfiability Problems
• On Syntactic versus Computational Views of Approximability
• On the Approximation of Maximum Satisfiability
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• The complexity of theorem-proving procedures
• Approximation and Online Algorithms
• Local search characteristics of incomplete SAT procedures

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