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 ?
Obtaining Initial Estimates of the Value Assignment and Calibration Curve Slope for the Stochastic Approximation Algorithm
We have designed the polygon approximation algorithm and have analyzed the relation between the error and the number of polygon's edges.
In order to fulfil both the fault tolerance and energy efficiency requirements, we propose an efficient approximation algorithm, Energy Efficient Maximum Disjoint Coverage (EMDC), with provable approximation bound.
By using an approximation algorithm named Extended Hungarian is to minimize the number of steiner points on all the edges by means of extended cost in which the steiner points are calculated based on information about the nodes and the number of repeated values can be reduced.
For NP-hard problems, the research focuses on developing polynomial time approximation algorithms. Given instance I of a minimization problem and approximation algorithm A, let A(I) and OPT(1) denote the objective value of the solution obtained by algorithm A and the optimal solution value, respectively, when applied to I.
They give an approximation algorithm for this problem when the sensor ranges are unit disks.
As discussed in the introduction, the best approximation algorithm for the densest k-subgraph problem currently known has an approximation ratio of O([n.sup.1/4+[delta]]) for any fixed [delta] > 0 [4] and it is conjectured that the inapproximability of the problem is of a similar magnitude.
In [19], an 0(n log n) time 12-factor approximation algorithm is proposed for the problem of covering a set of line segments with minimum number of sensors.
Zhu, "Optimized approximation algorithm in neural networks without overfitting," IEEE Transactions on Neural Networks, vol.
In the last few years, there has been renewed interest in tackling this problem, this time from the perspective of approximation algorithms.(2) In this paper, we carry this further by developing an approximation algorithm based on the primal-dual schema.
IS is approximate equivalent to SP, in the sense that every approximation algorithm solving the former also solves the latter within the same approximation ratio; this equivalence becomes very clear and intuitive by means of a graph (see Definition 3 at the beginning of Part II) defined for every SP-instance; proofs of this equivalence are found in Berge [1973] and Simon [1990].