Local Search to Approximate Max NAE-$$k$$-Sat Tightly
From MaRDI portal
Publication:3452574
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
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
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
