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 ?
We have designed the polygon approximation algorithm and have analyzed the relation between the error and the number of polygon's edges.
truncat] denote the error caused by approximation algorithm and truncation, respectively.
Again, Budgeted Maximum Conversion inherits a hardness due to Feige (1998): unless P = NP there is no approximation algorithm that can guarantee a solution strictly better than a (1 - 1/e) fraction of optimal.
Multi-Constrained Any-path routing as demonstrated in [5] presents a polynomial time K-approximation algorithm although fails to plan better approximation algorithm with strong hardness result on social networks.
proposed the core vector machine (CVM) [12,13] as the approximation algorithm of minimum enclosing ball (MEB) for large scale problems.
Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln |V (G)| + 1.
They give an approximation algorithm for this problem when the sensor ranges are unit disks.
In the first step of developing the approximation algorithm a set of neural networks were tested based on preliminary results given by [8].
The goal of an approximation algorithm is to come as close as possible to the optimum value in a reasonable amount of time which is at most polynomial time.
The algorithm in [28] is an approximation algorithm that has proven its efficiency in estimating large number of cycles in polynomial time when applied to real world networks.
As graphs show, the approximation algorithm FS performs best in terms of time measurement followed by the algorithm FSBE.
Parker and Rardin [13] presented an approximation algorithm, but did not report any computational experiment.