Hardness of approximation

MaRDI QIDQ5371213zbMATH OpenFDO

Authors Subhash Khot

Publication date 25 October 2017

zbMATH Keywords

approximation algorithmsdiscrete Fourier analysisinapproximabilityNP-completenessprobabilistically checkable proofs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 5971212
• On Khot’s unique games conjecture
• Approximability of hard combinatorial optimization problems: an introduction
• On the hardness of approximating Multicut and Sparsest-Cut
• The work of Subhash Khot

Cited in

(5)

• Hardness of fully dense problems
• The work of Subhash Khot
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Algorithms approaching the threshold for semi-random planted clique
• The moment-SOS hierarchy: applications and related topics

This page was built for publication: Hardness of approximation

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