Local Search to Approximate Max NAE-$$k$$-Sat Tightly

DOI10.1007/978-3-319-19647-3_25zbMath1356.68209OpenAlexW2403884680MaRDI QIDQ3452574

Kaiyuan Zhu, Lianrong Pu, Aiyong Xian, Daming Zhu

Publication date: 12 November 2015

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-19647-3_25

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Local Search to Approximate Max NAE-$$k$$-Sat Tightly