Approximation Algorithm
Domain: Algorithms
🎯 Motivation
For NP-hard problems where finding the exact optimal is too slow, approximation algorithms find a ‘good enough’ solution with a guaranteed quality bound.
📋 Concrete Example
Travelling salesman is NP-hard. A 2-approximation algorithm guarantees a route at most twice the optimal length, in polynomial time. Not perfect, but guaranteed to be decent.
🔗 Analogy
Packing a suitcase: finding the perfect arrangement (optimal) might take hours. A quick heuristic gets a ‘good enough’ packing in minutes that is at most slightly worse.