LearnViz CompSci
Home / Learn / Theory & Discrete Math / Approximation and Inapproximability

Advanced Topic 43 of 51 Theory & Discrete Math

Approximation and Inapproximability

Limits on how closely hard problems can be approximated.

How it works

Approximation theory studies how well NP-hard optimization problems can be solved in polynomial time. An alpha-approximation algorithm guarantees a solution within a factor alpha of optimal. Some problems have polynomial-time approximation schemes, achieving any factor 1 plus epsilon, such as Euclidean traveling salesman; others have constant-factor algorithms, like 2-approximation for vertex cover; and some cannot be approximated within certain factors unless P equals NP, such as general clique and set cover below a logarithmic factor. The PCP theorem underlies many inapproximability proofs through gap reductions.

Step-by-step walkthrough

  1. For many hard problems exact solutions are intractable.
  2. Approximation algorithms give guarantees, such as within a factor of 2.
  3. Some problems cannot be approximated well unless P equals NP.
  4. The PCP theorem proves such gaps.
  5. The knowledge shows when to stop trying for better.

Where it is used

Logistics, network design, scheduling and clustering use approximation algorithms with proven guarantees when exact solutions are infeasible.

Common pitfall

Worst-case ratios may be pessimistic, and heuristics often do better on real data. Hardness of approximation results show certain ratios are impossible unless complexity assumptions fail. Distinguish minimization from maximization conventions, where ratios are above or below one. Understand which approximation class a problem falls in before investing in algorithm design.

Where it fits in the course

Approximation and Inapproximability is topic 43 of 51 in Theory & Discrete Math, rated Advanced. It follows Randomized Complexity. The next topic is Parameterized Complexity.

Practice and explore

How to study this topic

  1. Read the explanation above and restate the definition in your own words.
  2. Open the interactive lesson and answer its mini quiz.
  3. Read the common pitfall, then write a short example that avoids it.
  4. Check your understanding in the Theory & Discrete Math quiz, and revisit the topic if you miss a question.

Frequently asked questions

What is Approximation and Inapproximability?
Limits on how closely hard problems can be approximated. It belongs to Theory & Discrete Math and is an advanced-level topic.
Where do people use Approximation and Inapproximability?
Logistics, network design, scheduling and clustering use approximation algorithms with proven guarantees when exact solutions are infeasible.
What is the most common mistake with Approximation and Inapproximability?
Worst-case ratios may be pessimistic, and heuristics often do better on real data.
What should I learn before this topic?
Start with Randomized Complexity, the topic just before it in Theory & Discrete Math.
How can I practice it?
Answer the mini quiz in the interactive lesson, then take the Theory & Discrete Math quiz.
Is Approximation and Inapproximability hard to learn?
It is an Advanced topic. Expect to read the explanation more than once and to connect it with earlier topics. Working through a small example by hand helps most.
How long does it take to learn Approximation and Inapproximability?
Most learners can read the explanation and finish the interactive lesson in under an hour. Fluency comes from applying the idea, so plan a few short practice sessions with the quiz.
Which topics are related to Approximation and Inapproximability?
Randomized Complexity, Parameterized Complexity, Space Complexity Classes are closely connected. The full list is in the related topics section of this page.
What should I study after Approximation and Inapproximability?
Continue with Parameterized Complexity, the next topic in Theory & Discrete Math.

Related topics