scientific article; zbMATH DE number 1775419

MaRDI QIDQ4542552zbMATH OpenFDO

Authors Sanjeev Arora

Publication date 1 August 2002

zbMATH Keywords

CHROMATIC NUMBERMAX-3SATMAX-CLIQUEPCP-based inapproximabilitySET-COVER

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• The inapproximability of non-NP-hard optimization problems.
• scientific article; zbMATH DE number 1256636
• On the hardness of approximating minimization problems
• Inapproximability of combinatorial optimization problems
• scientific article; zbMATH DE number 1330033

Cited in

(33)

• Easy NP-hardness Proofs of Some Subset Choice Problems
• The Complexity and Distribution of Hard Problems
• scientific article; zbMATH DE number 5787962 (Why is no real title available?)
• scientific article; zbMATH DE number 1263206 (Why is no real title available?)
• The Fault Tolerance of NP-Hard Problems
• Some recent strong inapproximability results
• Embracing the giant component
• Interactive and probabilistic proof-checking
• On the hardness of approximating minimization problems
• The inapproximability of non-NP-hard optimization problems.
• Relation between the hardness of a problem and the number of its solutions
• Approximation algorithms for NP-hard problems
• A computational-level explanation of the speed of goal inference
• On Unapproximable Versions of $NP$-Complete Problems
• On the Effective Enumerability of NP Problems
• The hardness of approximation: Gap location
• Approximate counting and NP search problems
• scientific article; zbMATH DE number 1405801 (Why is no real title available?)
• The work of Subhash Khot
• Rational analysis, intractability, and the prospects of `as if'-explanations
• Approximate solution of NP optimization problems
• scientific article; zbMATH DE number 1670535 (Why is no real title available?)
• Polynomial approximation algorithms with performance guarantees: an introduction-by-example
• The NP-completeness column: the many limits on approximation
• Improved approximations for hard optimization problems via problem instance classification
• Hardness of fully dense problems
• NP-completeness of the Hamming salesman problem
• Inapproximability of combinatorial optimization problems
• A computational complexity analysis of tunable type inference for Generic Universe Types
• Algebraic testing and weight distributions of codes.
• scientific article; zbMATH DE number 847149 (Why is no real title available?)
• A Theory of NP-completeness and Ill-conditioning for Approximate Real Computations
• UG-hardness to NP-hardness by losing half

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 Q4542552)