scientific article; zbMATH DE number 1258327

MaRDI QIDQ4229151zbMATHFDO

Authors Guillermo Morales Luna, Guillermo de Ita Luna

Publication date 9 March 1999

Full work available at URL http://www.emis.de/proceedings/3ICAOC/

zbMATH Keywords

complexityNP-completenessSAT problemapproximation theory for NP-completeness

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1552232
• scientific article; zbMATH DE number 1002206
• Approximation algorithms for the maximum satisfiability problem
• scientific article; zbMATH DE number 1302170
• On Some Recent Approximation Algorithms for MAX SAT
• Sums of squares based approximation algorithms for MAX-SAT
• On the Approximation of Maximum Satisfiability
• Improved approximation algorithms for MAX SAT
• Publication:4952605

Cited in

(25)

• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 6129431 (Why is no real title available?)
• An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
• Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT
• MAX SAT approximation beyond the limits of polynomial-time approximation
• Automata, Languages and Programming
• Complexity and Approximability of Parameterized MAX-CSPs
• Further Reflections on a Theory for Basic Algorithms
• scientific article; zbMATH DE number 1304324 (Why is no real title available?)
• Near-optimal algorithms for maximum constraint satisfaction problems
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• On the hardness of approximating max-satisfy
• scientific article; zbMATH DE number 1979498 (Why is no real title available?)
• Simple Approximation Algorithms for Balanced MAX 2SAT
• On Some Recent Approximation Algorithms for MAX SAT
• A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• Approximation algorithms for Max Morse matching
• scientific article; zbMATH DE number 6381632 (Why is no real title available?)
• Sums of squares based approximation algorithms for MAX-SAT
• On Approximation Algorithms for Hierarchical MAX-SAT
• scientific article; zbMATH DE number 1552232 (Why is no real title available?)
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• Approximating a generalization of MAX 2SAT and MIN 2SAT
• Approximating MAX SAT by moderately exponential and parameterized algorithms

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4229151)