approximation algorithm

(redirected from Approximation algorithms)

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 ?
Two approximation algorithms were designed with the polynomial running times.
The topics include the greedy-base construction of load-balanced virtual backbones, approximation algorithms for load-balanced virtual backbone construction, constructing load-balanced virtual backbones in probabilistic wireless sensor networks with a multi-objective genetic algorithm, reliable and energy efficient target coverage, snapshot and continuous data collection in dual radio-multi-channel wireless sensor networks based on connected dominating sets, and broadcast scheduling in cognitive radio networks.
They proposed some approximation algorithms for this problem with the complex, cost-related criterion.
At present, the algorithms used in production scheduling can be divided into accurate algorithms and approximation algorithms. Accurate algorithms (mathematical programming, branch and bound algorithm, Lagrangian relaxation, etc.) can get accurate solutions of problems, but big amount of calculation and time-consumption limit their applications in solving small-scale problems.
Therefore, to solve such problems in practice, approximation algorithms are applied most commonly.
To solve the TSP, there are algorithms in the literature deterministic (exact) and approximation algorithms (heuristics).
Using of AForge.Neuro allows creating an application in Microsoft Visual C# environment according to specific requirements for implementation of approximation algorithms into control system supporting C#.
The research presents fast approximation algorithms based on heuristics that work well in practice for large problem instances and compare the results with Optimal Naive algorithm.
A group of European contributors classify scheduling problems and their complexity, and present examples that show effective techniques for the design of efficient approximation algorithms, classical problems such as the makepsan minimization problem, and recent advances such as energy-efficient scheduling algorithms.
(11) have designed an approximation algorithms with small constant factors for this problem.
Then, we can use approximation algorithms for set-covering problem such as the greedy algorithm or primal-dual schema proposed in [18] to compute the minimum number of representative graph patterns.
The best previously known approximation algorithms are based on LP relaxations in time or interval-indexed variables.