Max NP-completeness made easy
type: Item
instance of: scholarly article
title: Max NP-completeness made easy
zbMATH Open document ID: 0933.68060
DOI: 10.1016/S0304-3975(98)00200-X
author: Pilu Crescenzi
author: Luca Trevisan
published in: Theoretical Computer Science
publication date: 2000-01-12T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1387543
zbMATH Keywords: approximation algorithms
zbMATH Keywords: approximation preserving reductions
zbMATH Keywords: class Max NP
zbMATH Keywords: probabilistic method
MaRDI profile type: Publication
cites work: Structure preserving reductions among convex optimization problems
cites work: Q4230322
cites work: Q4004078
cites work: Probabilistic checking of proofs
cites work: Q4039803
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Q4293543
cites work: Q4252727
cites work: Q4734761
cites work: A linear time algorithm for finding tree-decompositions of small treewidth
cites work: Completeness in approximation classes
cites work: Q4470516
cites work: Q4058132
cites work: Q4198056
cites work: New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
cites work: Q4526964
cites work: Q4470517
cites work: Approximation algorithms for combinatorial problems
cites work: Q4228486
cites work: Logical definability of NP optimization problems
cites work: Approximation properties of NP minimization classes
cites work: Q3221403
cites work: Non deterministic polynomial optimization problems and their approximations
cites work: Quantifiers and approximation
cites work: Optimization, approximation, and complexity classes
cites work: Continuous reductions among combinatorial optimization problems
cites work: On the Approximation of Maximum Satisfiability
Recommended article: A simplified NP-complete MAXSAT problem
Recommended article: On the NP-Hardness of Max-Not-2
Recommended article: On the hardness of approximating max-satisfy
Recommended article: A simplified NP-complete satisfiability problem
Recommended article: NP-completeness: A retrospective
Recommended article: Q4035692
Recommended article: NP-completeness of a combinator optimization problem
Recommended article: The complexity of selecting maximal solutions
Recommended article: More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
description: scientific article; zbMATH DE number 1387543