approximation algorithm

(redirected from Approximation ratio)

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.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
Mentioned in ?
References in periodicals archive ?
[9] improved the approximation ratio to O(1/[[epsilon].sup.5]) with capacity violation of (1 + [epsilon]) for the same version of the problem.
(iii) We propose an efficient bounded approximation algorithm, the EMDC, to the minimum [E.sub.relay] energy coverage problem and present an appropriate theoretical analysis of the EMDC approximation ratio.
Finally, we have the algorithm from [24] that works out a solution with a constant approximation ratio for MCLP in monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant.
It can be seen from Figure 4 that the approximation ratio of second-order nonlinear dynamic system based on cubic spline interpolation function is better than other numeric methods, which avoids the Runge phenomenon on account of the limitation of the interpolation condition.
The former ratio here is called the proximity degree in [5], and is part of the definition of a z-approximation in [14]; the latter is called a differential approximation ratio in [11, 10].
In [23], Kesselheim improved the result obtained in [22] and developed the first O(1) approximation ratio algorithm for MLS with power control.
In the context of CDS construction, the approximation ratio of an algorithm A is defined as the largest (worst) ratio between the size of the obtained CDS using algorithm A and the optimal result that can be obtained by MCDS (opt).
This elegant algorithm gives the same running time and approximation ratio as the algorithm presented in this paper.
However, we show that the approximation ratio achievable using the corresponding linear program relaxation cannot be better than D.
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].
--The Approximation Ratio (AR) is the ratio between the area that our algorithm approximately describes of a hole and the true area of this hole.
If A(1)/OPT(1) [less than or equal to] [rho] for all I, then we say that algorithm A has approximation ratio [rho], and A is called [rho]-approximation algorithm for this problem.