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

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

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

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

complexity; algorithm; local search; satisfiability; performance ratio

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68W25: Approximation algorithms

Uses Software

• Outward rotations