approximation algorithm


Also found in: Wikipedia.

approximation algorithm

(algorithm)
An algorithm for an optimisation problem that generates feasible but not necessarily optimal solutions.

Unlike "heuristic", the term "approximation algorithm" often implies some proven worst or average case bound on performance. The terms are often used interchangeably however.
Mentioned in ?
References in periodicals archive ?
The Greedy Approximation algorithm 'G (V, E)' achieves higher approximation with the least collision factor in MANET.
The approximation algorithm is proposed in [31, 30], where we show its efficiency and effectiveness.
Parker and Rardin [13] presented an approximation algorithm, but did not report any computational experiment.
A linear time 2 + e approximation algorithm for edge connectivity.
7) proposed no polynomial time approximation algorithm for the terminal Steiner tree problem has a performance ratio less then (1 - [OMICRON](1)) ln n unless NP has slightly superpolynomial time algorithms.
E], and then use an approximation algorithm to solve a set-covering problem with a smaller size.
In this paper, we study the notion of a combinatorial dominance guarantee as an alternate performance measure for assessing the quality of a given heuristic or approximation algorithm.
Terminology (1) Two-dimensional FFT Accelerator: DAPDNA-2 implementing HIO algorithm for phase retrieval, enabling high speed processing (2) DAPDNA: Digital Application Processor, Distributed Network Architecture (3) Dynamically Reconfigurable Processor: processor capable of dynamically switching among prepared circuit configurations in a single clock cycle (4) HIO algorithm: Successive approximation algorithm developed in Stanford University, it enables image reproduction through four steps: Fourier transform, reciprocal space constraint, reverse Fourier transform, and real space constraint.
In the first way, a stochastic approximation algorithm together with a stopping rule iteratively finds the appropriate analyte level for a standard prepared from a reference material that will yield the same average signal response as the new production calibrator, whose concentration is not precisely known at the time of manufacture; the value assignment of the production calibrator is then the analyte level of the reference standard at the final iteration of the algorithm.
31 give a constant-factor approximation algorithm with O(nt log nt) running time, where t is the diameter of P.
The Recursive Low-Rank Hankel (RLRH) approximation algorithm is presented.
With this approximation algorithm, creating the guide line for the whole cooling system not only is sensitive to part geometry but also ensures the conformal characteristics of the cooling channel.