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.
Mentioned in ?
References in periodicals archive ?
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.
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.
This elegant algorithm gives the same running time and approximation ratio as the algorithm presented in this paper.
This algorithm achieves an approximation ratio of (1 + DF/k).
Either IS can be solved by a polynomial time approximation schema, or there is no polynomial time approximation algorithm for IS achieving an approximation ratio bounded below by a fixed positive constant.
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.
10 which gives a constant approximation ratio of 1 - 1/4 + 2lnk/[k.
10 which gives a constant approximation ratio of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for MAX H-COL, when the graph H has clique number r and chromatic number k.
The Held-Karp heuristic is conjectured to have an approximation ratio 4/3 (some results of Goemans [1995] support this conjecture) but the best upperbound known is 3/2 (Wolsey [1980], Shmoys and Williamson [1990]).