DataTerminology.comNEW
Algorithm that returns near-optimal solutions to hard optimization problems with provable bounds on solution quality or runtime.
DESCRIPTION
Approximation algorithms provide efficient, theoretically grounded solutions for optimization problems that are computationally intractable to solve exactly at scale. They typically offer provable performance guarantees, such as an approximation ratio relative to the optimum. Techniques include greedy methods, LP relaxations with rounding, primalādual methods, and submodular maximization. These algorithms are widely used for routing, scheduling, facility location, clustering, and influence maximization. Unlike heuristics, approximation algorithms come with mathematical guarantees, trading exactness for predictable quality.
ALTERNATIVE DEFINITIONS
Wikipedia
In computer science and operations research, an approximation algorithm is an algorithm for finding approximate solutions to optimization problems.
Highlights the focus on optimization problems and approximate solutions.
NIST Dictionary of Algorithms and Data Structures
An approximation algorithm is an algorithm that finds an approximate solution to an optimization problem.
Concise definition from a curated algorithms glossary.
RELATED TERMS
NP-Hardness Greedy Algorithm Approximation Ratio Polynomial-Time Approximation Scheme Randomized Algorithm Linear Programming Relaxation Metaheuristics Submodular Optimization Fully Polynomial-Time Approximation Scheme
COMPETING TERMS
Exact Algorithm Heuristic Algorithm
RELATIONS
- Broader: Algorithm
KNOWLEDGE AREAS
Mathematics AI Data Science Software Engineering
TARGET AUDIENCE
Data Scientist AI Engineer Software Developer Software Architect Solution Architect
EXTERNAL SOURCES
- Wikipedia - Approximation algorithm
- MIT OpenCourseWare - Lecture notes including approximation algorithms
- Stanford University - Approximation algorithms lecture notes
TOP QUESTIONS
When should I use an Approximation Algorithm?
Use them when exact solutions are NP-hard or too slow at scale. They provide predictable quality with significantly lower runtime.
Category: Requirements
What is an approximation ratio?
It bounds how far an algorithmās solution can be from the optimal, e.g., a 2-approximation guarantees at most twice the optimal cost for minimization problems.
Category: Definition
How do Approximation Algorithms differ from heuristics?
Heuristics may work well empirically but lack guarantees. Approximation algorithms provide provable bounds on solution quality relative to the optimum.
Category: Misunderstanding
What techniques power Approximation Algorithms?
Common techniques include greedy strategies, linear programming relaxation and rounding, primalādual methods, and submodular maximization.
Category: Example
What problems benefit from Approximation Algorithms?
Classic problems like set cover, vertex cover, traveling salesperson (metric), facility location, and k-center have strong approximation results.
Category: Example
Are there limits to approximability?
Yes. Under complexity assumptions, some problems are hard to approximate within certain factors, characterized by PCP theorems and inapproximability results.
Category: Risk
Do Approximation Algorithms apply to maximization and minimization?
Yes. Ratios are defined accordingly, often as a multiplicative factor or additive error bound for both types.
Category: Definition
What is a PTAS?
A Polynomial-Time Approximation Scheme offers (1+Īµ)-approximate solutions for any Īµ>0 in time polynomial in input size but typically exponential in 1/Īµ.
Category: Definition
How relevant are Approximation Algorithms in practice?
They guide scalable designs with predictable outcomes, complementing heuristics in logistics, ad allocation, recommendations, and scheduling.
Category: Relevancy