Max NP-completeness made easy

DOI10.1016/S0304-3975(98)00200-XMaRDI QIDQ1960655zbMATH OpenFDO

Authors Pilu Crescenzi, Luca Trevisan

Publication date 12 January 2000

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

Full work available at URL https://doi.org/10.1016/S0304-3975(98)00200-X

zbMATH Keywords

approximation algorithmsprobabilistic methodapproximation preserving reductionsclass Max NP

Mathematics Subject Classification ID

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

Recommendations

• A simplified NP-complete MAXSAT problem
• On the NP-hardness of Max-Not-2
• On the NP-hardness of MAX-Not-2
• On the hardness of approximating max-satisfy
• A simplified NP-complete satisfiability problem
• NP-completeness: a retrospective
• scientific article; zbMATH DE number 176526
• NP-completeness of a combinator optimization problem
• The complexity of selecting maximal solutions
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256750 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1306875 (Why is no real title available?)
• scientific article; zbMATH DE number 578252 (Why is no real title available?)
• scientific article; zbMATH DE number 2077131 (Why is no real title available?)
• scientific article; zbMATH DE number 2077132 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• scientific article; zbMATH DE number 4121424 (Why is no real title available?)
• A linear time algorithm for finding tree-decompositions of small treewidth
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation algorithms for combinatorial problems
• Approximation properties of NP minimization classes
• Completeness in approximation classes
• Continuous reductions among combinatorial optimization problems
• Logical definability of NP optimization problems
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Non deterministic polynomial optimization problems and their approximations
• On the Approximation of Maximum Satisfiability
• Optimization, approximation, and complexity classes
• Probabilistic checking of proofs
• Quantifiers and approximation
• Structure preserving reductions among convex optimization problems

Cited in

(9)

• Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
• On MAX-SAT with cardinality constraint
• 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
• NP is as easy as detecting unique solutions
• More complicated questions about maxima and minima, and some closures of NP
• On MAX-SAT with cardinality constraint

This page was built for publication: Max NP-completeness made easy

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