Max NP-completeness made easy

DOI10.1016/S0304-3975(98)00200-XzbMath0933.68060MaRDI QIDQ1960655

Luca Trevisan, Pierluigi Crescenzi

Publication date: 12 January 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

probabilistic methodapproximation algorithmsapproximation preserving reductionsclass Max NP

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On the efficiency of polynomial time approximation schemes ⋮ Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat} ⋮ Sublinear-space approximation algorithms for Max \(r\)-SAT ⋮ A survey on the structure of approximation classes

Cites Work

• Completeness in approximation classes
• Continuous reductions among combinatorial optimization problems
• Structure preserving reductions among convex optimization problems
• Non deterministic polynomial optimization problems and their approximations
• Optimization, approximation, and complexity classes
• Quantifiers and approximation
• Approximation algorithms for combinatorial problems
• Logical definability of NP optimization problems
• Approximation properties of NP minimization classes
• Probabilistic checking of proofs
• Approximation algorithms for NP-complete problems on planar graphs
• On the Approximation of Maximum Satisfiability
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• A linear time algorithm for finding tree-decompositions of small treewidth
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item