approximation algorithm

(redirected from Approximation algorithms)
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 ?
One interesting family of problems is the design of heuristics for larger blocks and different substructures, and developing better approximation algorithms.
In this section we present the results of a few preliminary numerical experiments aimed at illustrating the performance of the approximation algorithms discussed in section 4, with particular attention to linear scaling behavior.
There have been some distributed approximation algorithms proposed in the literature for minimum WCDS.
Firstly, it aims to develop new graph algorithmic techniques, specifically in the areas of dynamic graph algorithms, online algorithms and approximation algorithms for graph-based optimization problems.
The types of actions are efficient digital filters, signal and spectrum analysis tricks, fast function approximation algorithms, signal generation techniques, and assorted high-performance digital signal processing techniques.
Further subjects include space-efficient identity based encryption without pairings, lower bounds on signatures from symmetric primitives, and approximation algorithms using hierarchies of semidefinite programming relaxations.
of Illinois-Urbana-Champagne) primarily describes some key techniques in geometric approximation algorithms, but also more traditional computational geometry techniques such as sampling and linear programming as they are widely used in developing the algorithms.
Reprints 28 articles originally published in IEEE signal processing magazine on digital filters, signal and spectrum analysis tricks, fast function approximation algorithms, signal generation techniques, and high-performance DSP techniques.
Papers from an October 2005 conference report on the latest work in the field, in areas such as the complexity of real functions, approximation algorithms for unique games, a recursive greedy algorithm for walks in directed graphs, additive approximation for edge-deletion problems, and quantum information and the PCP theorem.
Handbook of approximation algorithms and metaheurististics.
Due to this difficulty, and growth of problem size the focus of the researcher has turned to approximation algorithms such as heuristics and meta-heuristics (genetic algorithms, simulated annealing, and Tabu search) instead of exact methods which has become inapplicable in practice[5].
The broader impact of this study spans a better understanding of limits for approximation algorithms saving time and resources for algorithm designers; and new understanding of robustness in a variety of mathematical contexts, arising from the many connections between PCPs and stability questions in combinatorics, functional analysis, metric embeddings, probability, and more.