Deriving non-approximability results by reductions

DOI10.1007/BFb0053018zbMath1401.68101MaRDI QIDQ4571893

Hein Rohrig, Claus Rick

Publication date: 3 July 2018

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

Mathematics Subject Classification ID

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