Hardness of approximation, aka inapproximability.

This tag is for questions related to hardness of approximation (also called inapproximability) of optimization problems.

  • Please consider adding also .
  • Questions specifically related to probabilistically checkable proofs are better tagged as .
  • Questions about approximation algorithms rather than hardness should be tagged as .
  • Questions about NP-hardness of solving optimization problems exactly rather than approximately should be tagged as .
history | excerpt history