Publication:3096713
From MaRDI portal
zbMath1252.68143MaRDI QIDQ3096713
Publication date: 11 November 2011
Full work available at URL: http://ebooks.worldscinet.com/ISBN/9789814324359/9789814324359_0163.html
NP-completeness; approximation algorithms; probabilistically checkable proofs; discrete Fourier analysis; inapproximability
68-02: Research exposition (monographs, survey articles) pertaining to computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Reoptimization of constraint satisfaction problems with approximation resistant predicates, On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field, Vertical perimeter versus horizontal perimeter