LearnViz CompSci
Home / Learn / Algorithms / Approximation Algorithms

Advanced Topic 47 of 51 Algorithms

Approximation Algorithms

Methods guaranteeing near-optimal answers to hard problems.

How it works

Approximation algorithms give provably near-optimal solutions to NP-hard optimization problems in polynomial time. Their quality is measured by an approximation ratio, the worst-case factor between the returned value and the true optimum. For example, a simple algorithm gives a 2-approximation for vertex cover, and Christofides gives 1.5 for metric traveling salesman. Some problems have approximation schemes, and others cannot be approximated well unless P equals NP.

Step-by-step walkthrough

  1. The exact problem is NP-hard, so no fast exact method is known.
  2. A polynomial-time algorithm gives an answer quickly.
  3. The answer is provably within a factor of the optimal, such as at most twice.
  4. Vertex cover by taking both ends of maximal matching edges is a 2-approximation.
  5. The guarantee holds for every input.

Where it is used

Network design, scheduling, facility location, vertex cover, set cover and routing logistics where exact solutions are too slow use approximation algorithms.

Common pitfall

The worst-case ratio may be far from the typical case, and heuristics without guarantees can be much worse. Some practical solvers beat theoretical ratios. Be careful with minimization versus maximization when stating ratios. Verify that the problem structure, such as the triangle inequality, is satisfied.

Where it fits in the course

Approximation Algorithms is topic 47 of 51 in Algorithms, rated Advanced. It follows Randomized Algorithms. The next topic is Amortized Analysis.

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 Algorithms quiz, and revisit the topic if you miss a question.

Frequently asked questions

What is Approximation Algorithms?
Methods guaranteeing near-optimal answers to hard problems. It belongs to Algorithms and is an advanced-level topic.
Where do people use Approximation Algorithms?
Network design, scheduling, facility location, vertex cover, set cover and routing logistics where exact solutions are too slow use approximation algorithms.
What is the most common mistake with Approximation Algorithms?
The worst-case ratio may be far from the typical case, and heuristics without guarantees can be much worse.
What should I learn before this topic?
Start with Randomized Algorithms, the topic just before it in Algorithms.
How can I practice it?
Answer the mini quiz in the interactive lesson, then take the Algorithms quiz.
Is Approximation Algorithms 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 Algorithms?
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 Algorithms?
Randomized Algorithms, Amortized Analysis, Huffman Coding are closely connected. The full list is in the related topics section of this page.
What should I study after Approximation Algorithms?
Continue with Amortized Analysis, the next topic in Algorithms.

Related topics