scientific article; zbMATH DE number 1258327

zbMATH Open0912.68036MaRDI QIDQ4229151FDOQ4229151

Guillermo Morales Luna, Guillermo de Ita Luna

Publication date: 9 March 1999

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

Title of this publication is not available (Why is that?)

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)

Cited In (24)

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

Recommendations

• On the Approximation of Maximum Satisfiability 👍 👎
• Approximation algorithms for the maximum satisfiability problem 👍 👎
• On Some Recent Approximation Algorithms for MAX SAT 👍 👎
• Improved approximation algorithms for MAX SAT 👍 👎
• Sums of squares based approximation algorithms for MAX-SAT 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)