Home›Optimization Algorithm›Design Technique›Approximation AlgorithmsConceptApproximation AlgorithmsTechniqueReference and ClassificationDevelopingApproximation 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.FactsApproximation AlgorithmsConnectionsSourcesComments (0)Reader Challenges (0)FactsCore PrincipleWell-attestedRun in polynomial time and output a solution guaranteed to be close to the optimal solution of an optimization problem. 1Approximation AlgorithmsFilter Results30 entriesCategoryAllApproximation Algorithms (4)Constraint-Based Planning and Generation Algorithms (1)Metaheuristic Optimization Algorithms (12)Numerical Search and Equilibrium Methods (1)Time ComplexityAllPolynomial Time -- O(n^k) (2)Quadratic Time -- O(n^2) (1)Invented ByAllBruce Donald (1)Marco Dorigo (1)GroupAllApproximation Algorithms (4)Constraint-Based Planning and Generation Algorithms (1)Metaheuristic Optimization Algorithms (12)Numerical Search and Equilibrium Methods (1)Credited ToAllBruce Donald (1)Marco Dorigo (1)ACM AreaAllAlgorithms and Complexity Theory (10)Computational Science (1)Evolutionary Computation (10)Robotics (1)Show ResultsBrowseCompareSelect all 302-Opt AlgorithmApproximation AlgorithmsAnt Colony Optimization AlgorithmApproximation AlgorithmsAPXApproximation AlgorithmsArtificial Bee Colony AlgorithmApproximation AlgorithmsBat AlgorithmApproximation AlgorithmsCuckoo Search AlgorithmApproximation AlgorithmsDifferential EvolutionApproximation AlgorithmsFirefly AlgorithmApproximation AlgorithmsFully polynomial-time approximation schemeApproximation AlgorithmsGreedy Randomized Adaptive Search ProcedureApproximation AlgorithmsGrey Wolf OptimizerApproximation AlgorithmsHarmony Search AlgorithmApproximation AlgorithmsHill Climbing AlgorithmApproximation AlgorithmsK-Approximation of K-Hitting SetApproximation AlgorithmsKarloff-Zwick AlgorithmApproximation AlgorithmsKinodynamic PlanningApproximation AlgorithmsLin-Kernighan AlgorithmApproximation AlgorithmsLion AlgorithmApproximation AlgorithmsMethod of Conditional ProbabilitiesApproximation AlgorithmsMulti-Fragment AlgorithmApproximation AlgorithmsNelder-Mead Method AlgorithmApproximation AlgorithmsParameterized approximation algorithmApproximation AlgorithmsParticle Swarm Optimization AlgorithmApproximation AlgorithmsPolynomial-time approximation schemeApproximation AlgorithmsRandomized RoundingApproximation AlgorithmsSimulated Annealing AlgorithmApproximation AlgorithmsSubmodular set functionApproximation AlgorithmsTabu Search AlgorithmApproximation AlgorithmsVariable Neighborhood SearchApproximation AlgorithmsWhale Optimization AlgorithmApproximation AlgorithmsConnectionsIn FieldAlgorithms and Complexity Theory, Fields Well-attested Technique Used By2-Opt Algorithm, Algorithms Well-attested A* Search Algorithm, Algorithms Well-attested Ant Colony Optimization Algorithm, Algorithms Well-attested APX, Algorithms Well-attested Artificial Bee Colony Algorithm, Algorithms Well-attested Bat Algorithm, Algorithms Well-attested BLAST (Biotechnology), Algorithms Well-attested Christofides Algorithm, Algorithms Well-attested Contraction Hierarchies Algorithm, Algorithms Well-attested Convex Volume Approximation, Algorithms Well-attested Coreset, Algorithms Well-attested Cuckoo Search Algorithm, Algorithms Well-attested DIAMOND (biotechnology), Algorithms Well-attested Differential Evolution, Algorithms Well-attested Farthest-First Traversal, Algorithms Well-attested Firefly Algorithm, Algorithms Well-attested Fully polynomial-time approximation scheme, Algorithms Well-attested Greedy Randomized Adaptive Search Procedure, Algorithms Well-attested Grey Wolf Optimizer, Algorithms Well-attested Harmony Search Algorithm, Algorithms Well-attested Hill Climbing Algorithm, Algorithms Well-attested Iterative Deepening A* Algorithm, Algorithms Well-attested K-Approximation of K-Hitting Set, Algorithms Well-attested Karloff-Zwick Algorithm, Algorithms Well-attested Kernighan-Lin algorithm, Algorithms Well-attested Kinodynamic Planning, Algorithms Well-attested Source Wikipedia: Kinodynamic planningK-Means Clustering Algorithm, Algorithms Well-attested K-means++, Algorithms Well-attested Source K-means++ (Wikipedia)Lin-Kernighan Algorithm, Algorithms Well-attested Lion Algorithm, Algorithms Well-attested Method of Conditional Probabilities, Algorithms Well-attested Minimum k-Cut, Algorithms Well-attested Monte Carlo Tree Search, Algorithms Well-attested Multi-Fragment Algorithm, Algorithms Well-attested Neighbor joining, Algorithms Well-attested Nelder-Mead Method Algorithm, Algorithms Well-attested Parameterized approximation algorithm, Algorithms Well-attested Particle Swarm Optimization Algorithm, Algorithms Well-attested Polynomial-time approximation scheme, Algorithms Well-attested Pseudo-LRU, Algorithms Well-attested Source Pseudo-LRU (Wikipedia)Randomized Rounding, Algorithms Well-attested Simulated Annealing Algorithm, Algorithms Well-attested Submodular set function, Algorithms Well-attested Tabu Search Algorithm, Algorithms Well-attested Variable Neighborhood Search, Algorithms Well-attested Vertex k-Center Problem, Algorithms Well-attested Whale Optimization Algorithm, Algorithms Well-attested Sources1. NIST DADS: approximation algorithmDefinitionQuote, DefinitionAn 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 SourceWikipedia: Approximation algorithmWikipedia, lead sectionapproximation 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, LeadIn 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 SourceWikipedia: Kinodynamic planningTechnique Used By: Kinodynamic Planning, LeadQuote, Technique Used By: Kinodynamic Planning, LeadDonald et al. developed the first polynomial-time approximation schemes (PTAS) for the problem.View the SourceK-means++ (Wikipedia)Technique Used By: K-means++, LeadQuote, Technique Used By: K-means++, Leadas an approximation algorithm for the NP-hard k-means problemView the SourcePseudo-LRU (Wikipedia)Technique Used By: Pseudo-LRU, LeadQuote, Technique Used By: Pseudo-LRU, Leadby replacing values using approximate measures of age rather than maintaining the exact age of every value in the cacheView the SourceComments (0)No comments yet. Be the first to share a thought.Sign in to join the discussion.Reader Challenges (0)No disputes yet. Spotted an error or a better source? Open the first one.Sign in to dispute this or suggest a correction.