What are Approximation Algorithms and When Do You Use Them?
Learn what approximation algorithms are, how approximation ratios work, and when to use them for NP-hard problems in interviews.
Expected Interview Answer
An approximation algorithm trades exact optimality for polynomial-time runtime by finding a solution provably within a bounded factor of the optimal — such as a 2-approximation guaranteeing a result no worse than twice the true optimum — and is the standard engineering response to NP-hard optimization problems where an exact solution is computationally infeasible at scale.
Unlike a heuristic, which offers no formal guarantee on solution quality, an approximation algorithm comes with a proven bound relating its output to the true optimum, expressed as an approximation ratio like 2-approximation or (1 + epsilon)-approximation. Classic examples include the greedy 2-approximation for vertex cover, the 2-approximation for metric TSP using minimum spanning trees, and the polynomial-time approximation scheme (PTAS) for the knapsack problem that gets arbitrarily close to optimal at the cost of exponentially more time as epsilon shrinks. Choosing to use one is a direct consequence of recognizing a problem is NP-hard: since no known polynomial exact algorithm exists, an approximation algorithm gives a mathematically defensible tradeoff between solution quality and runtime that a plain heuristic cannot promise. In production systems, approximation algorithms are preferred over unguaranteed heuristics whenever the business needs a provable worst-case bound on how far off the answer can be, such as in resource allocation, network design, or scheduling under SLA constraints.
- Provides a provable worst-case bound instead of an unguaranteed guess
- Runs in polynomial time on problems where exact solutions are NP-hard
- Lets engineers reason formally about how far a result is from optimal
- Scales to large inputs where brute-force or dynamic programming is infeasible
AI Mentor Explanation
Finding the mathematically optimal batting order against every possible bowling change is NP-hard-flavored and too slow to compute before a match. A greedy approximation instead picks the best available batter for each slot in order, and a coach can mathematically prove this greedy order never scores worse than half of the theoretical best lineup's total, which is the cricket equivalent of a 2-approximation. This is different from a gut-feel heuristic pick with no guarantee at all — the coach can point to a provable bound, not just intuition. Selectors use exactly this tradeoff under real match-day time pressure, choosing a provably bounded-good order over an exhaustive, unaffordable search.
Step-by-Step Explanation
Step 1
Confirm the exact problem is NP-hard
Establish that no known polynomial-time exact algorithm exists for the optimization problem at hand.
Step 2
Design a polynomial-time approximation
Build a greedy, LP-relaxation, or spanning-tree-based algorithm that runs fast and returns a feasible solution.
Step 3
Prove the approximation ratio
Mathematically bound the algorithm's output relative to the true optimum, e.g. never worse than 2x optimal.
Step 4
Validate the bound holds in practice
Benchmark against known-optimal small instances or LP lower bounds to confirm the theoretical ratio matches real behavior.
What Interviewer Expects
- Distinguish an approximation algorithm (provable bound) from a heuristic (no guarantee)
- Give at least one concrete example with its stated ratio, like the 2-approximation for vertex cover or metric TSP
- Explain the connection to NP-hardness: why exact polynomial algorithms are not expected to exist
- Discuss the tradeoff between approximation quality (epsilon) and runtime in a PTAS
Common Mistakes
- Using “approximation algorithm” and “heuristic” interchangeably
- Failing to state or understand what the approximation ratio actually bounds
- Assuming an approximation algorithm always gets close to optimal in practice, when it only guarantees a worst case
- Not connecting the need for approximation algorithms to the problem being NP-hard in the first place
Best Answer (HR Friendly)
“An approximation algorithm is what I reach for when a problem is too computationally hard to solve exactly in reasonable time, but I still need a mathematically defensible guarantee on how good my answer is, like promising it's never worse than double the true best result. It's different from just guessing, because I can actually prove the worst case, which matters a lot when stakeholders need to trust the numbers.”
Code Example
def approx_vertex_cover(edges):
# NP-hard to solve exactly (minimum vertex cover), but this greedy
# algorithm is a provable 2-approximation: it never returns a cover
# more than twice the size of the true minimum cover.
cover = set()
remaining = set(edges)
while remaining:
u, v = remaining.pop()
cover.add(u)
cover.add(v)
# Remove every edge touched by u or v -- this is why the bound holds:
# each pair added “pays for” at least one edge in any optimal cover.
remaining = {(a, b) for (a, b) in remaining if a not in (u, v) and b not in (u, v)}
return cover
edges = [("A", "B"), ("B", "C"), ("C", "D"), ("D", "A")]
print(approx_vertex_cover(edges)) # provably <= 2x the optimal cover sizeFollow-up Questions
- What is the difference between a PTAS and a plain constant-factor approximation algorithm?
- How would you prove an approximation ratio for a greedy algorithm?
- Why does metric TSP admit a 2-approximation but general TSP does not?
- When would you choose an unguaranteed heuristic over a formally bounded approximation algorithm?
MCQ Practice
1. What distinguishes an approximation algorithm from a plain heuristic?
An approximation algorithm has a mathematically proven approximation ratio; a heuristic offers no such formal guarantee.
2. A "2-approximation" algorithm for a minimization problem guarantees what?
A 2-approximation for a minimization problem bounds the output at no worse than 2x the optimal value, not a fixed additive difference.
3. Why do engineers reach for approximation algorithms on problems like vertex cover or metric TSP?
These problems are NP-hard, so exact polynomial-time solving is not expected; approximation algorithms give a fast, provably bounded alternative.
Flash Cards
What is an approximation algorithm? — A polynomial-time algorithm that returns a solution provably within a bounded factor of the true optimum for an NP-hard problem.
How does an approximation algorithm differ from a heuristic? — It comes with a formally proven bound on solution quality; a heuristic offers no such guarantee.
What does a "2-approximation" guarantee for a minimization problem? — The returned solution is never more than twice the value of the true optimal solution.
Name a classic approximation algorithm and its guarantee. — The minimum-spanning-tree-based algorithm for metric TSP is a 2-approximation.