scientific article; zbMATH DE number 1775419

zbMATH Open1028.68065MaRDI QIDQ4542552FDOQ4542552

Authors: Sanjeev Arora 

Publication date: 1 August 2002

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cited In (33)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Some recent strong inapproximability results
• The Fault Tolerance of NP-Hard Problems
• 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
• On Unapproximable Versions of $NP$-Complete Problems
• A computational-level explanation of the speed of goal inference
• On the Effective Enumerability of NP Problems
• The hardness of approximation: Gap location
• Approximate counting and NP search problems
• Title not available (Why is that?)
• The work of Subhash Khot
• Rational analysis, intractability, and the prospects of `as if'-explanations
• Title not available (Why is that?)
• Approximate solution of NP optimization problems
• 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
• Title not available (Why is that?)
• A Theory of NP-completeness and Ill-conditioning for Approximate Real Computations
• Algebraic testing and weight distributions of codes.
• UG-hardness to NP-hardness by losing half
• Easy NP-hardness Proofs of Some Subset Choice Problems
• The Complexity and Distribution of Hard Problems

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)