Optimal non-approximability of MaxClique

DOI10.1007/BFb0053019zbMath1401.68099OpenAlexW1537767152MaRDI QIDQ4571894

Anna Slobodová, Martin Mundhenk

Publication date: 3 July 2018

Published in: Lectures on Proof Verification and Approximation Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0053019

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)