Approximating Max NAE-k-SAT by anonymous local search
DOI10.1016/J.TCS.2016.05.040zbMATH Open1356.68210OpenAlexW2415155455MaRDI QIDQ507440FDOQ507440
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
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
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)
Cites Work
- Approximation algorithms for combinatorial problems
- Optimization, approximation, and complexity classes
- Title not available (Why is that?)
- The complexity of theorem-proving procedures
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Title not available (Why is that?)
- Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- Title not available (Why is that?)
- An algorithm based on tabu search for satisfiability problem
- Approximation and Online Algorithms
- Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
- On Syntactic versus Computational Views of Approximability
- On the Approximation of Maximum Satisfiability
- Improved approximations for max set splitting and max NAE SAT
- Tight bounds on local search to approximate the maximum satisfiability problems
- Tight bound on Johnson's algorithm for maximum satisfiability
- Improved approximation algorithms for MAX SAT
- Local search characteristics of incomplete SAT procedures
Cited In (1)
Uses Software
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)
