Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Concept

Approximation Algorithms

Technique

Approximation algorithms are, in computer science and operations research, efficient algorithms that find approximate solutions to optimization problems, in particular NP-hard problems, with provable guarantees on the distance of the returned solution to the optimal one. They arise naturally in theoretical computer science as a consequence of the widely believed conjecture that P does not equal NP, under which a wide class of optimization problems cannot be solved exactly in polynomial time. The field tries to understand how closely optimal solutions can be approximated in polynomial time, and in an overwhelming majority of cases the guarantee is a multiplicative one expressed as an approximation ratio or approximation factor. Algorithms recorded in this atlas are grouped here when their design technique is approximation.

Facts
Core Principle
Run in polynomial time and output a solution guaranteed to be close to the optimal solution of an optimization problem. 1
Connections

In Field

Algorithms and Complexity Theory, Fields

Technique Used By

2-Opt Algorithm, Algorithms
A* Search Algorithm, Algorithms
Ant Colony Optimization Algorithm, Algorithms
APX, Algorithms
Artificial Bee Colony Algorithm, Algorithms
Bat Algorithm, Algorithms
BLAST (Biotechnology), Algorithms
Christofides Algorithm, Algorithms
Contraction Hierarchies Algorithm, Algorithms
Convex Volume Approximation, Algorithms
Coreset, Algorithms
Cuckoo Search Algorithm, Algorithms
DIAMOND (biotechnology), Algorithms
Differential Evolution, Algorithms
Farthest-First Traversal, Algorithms
Firefly Algorithm, Algorithms
Fully polynomial-time approximation scheme, Algorithms
Greedy Randomized Adaptive Search Procedure, Algorithms
Grey Wolf Optimizer, Algorithms
Harmony Search Algorithm, Algorithms
Hill Climbing Algorithm, Algorithms
Iterative Deepening A* Algorithm, Algorithms
K-Approximation of K-Hitting Set, Algorithms
Karloff-Zwick Algorithm, Algorithms
Kernighan-Lin algorithm, Algorithms
Kinodynamic Planning, Algorithms
Source Wikipedia: Kinodynamic planning
K-Means Clustering Algorithm, Algorithms
Lin-Kernighan Algorithm, Algorithms
Lion Algorithm, Algorithms
Method of Conditional Probabilities, Algorithms
Minimum k-Cut, Algorithms
Monte Carlo Tree Search, Algorithms
Multi-Fragment Algorithm, Algorithms
Neighbor joining, Algorithms
Nelder-Mead Method Algorithm, Algorithms
Parameterized approximation algorithm, Algorithms
Particle Swarm Optimization Algorithm, Algorithms
Polynomial-time approximation scheme, Algorithms
Randomized Rounding, Algorithms
Simulated Annealing Algorithm, Algorithms
Submodular set function, Algorithms
Tabu Search Algorithm, Algorithms
Variable Neighborhood Search, Algorithms
Vertex k-Center Problem, Algorithms
Whale Optimization Algorithm, Algorithms
Sources
1. NIST DADS: approximation algorithm
Definition
Quote, Definition
An algorithm to solve an optimization problem that runs in polynomial time in the length of the input and outputs a solution that is guaranteed to be close to the optimal solution.
View the Source
Wikipedia: Approximation algorithm
  • Wikipedia, lead section
    approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one.
  • In Group: Algorithm Design Strategies, Lead
    In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one.
View the Source
Wikipedia: Kinodynamic planning
Technique Used By: Kinodynamic Planning, Lead
Quote, Technique Used By: Kinodynamic Planning, Lead
Donald et al. developed the first polynomial-time approximation schemes (PTAS) for the problem.
View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.