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.
Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty
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.
Wireless ad hoc and sensor networks; management, performance, and applications
They proposed some approximation algorithms for this problem with the complex, cost-related criterion.
INTEGRATION POLICIES FOR PREVENTIVE MAINTENANCE AND REPAIRS OF COMPLEX FLOW SHOP
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.
Full glowworm swarm optimization algorithm for whole-set orders scheduling in single machine
Therefore, to solve such problems in practice, approximation algorithms are applied most commonly.
Applying metaheuristic strategies in construction projects management
To solve the TSP, there are algorithms in the literature deterministic (exact) and approximation algorithms (heuristics).
Analyzing the performance of mutation operators to solve the traveling salesman problem
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#.
Approximation of CO/lambda biomass combustion dependence by artificial intelligence techniques
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.
Designing a product to maximize visibility
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.
Introduction to scheduling
(11) have designed an approximation algorithms with small constant factors for this problem.
An efficient algorithm to compute a Steiner set and Steiner tree on trapezoid graphs
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.
Clustering frequent graph patterns
The best previously known approximation algorithms are based on LP relaxations in time or interval-indexed variables.
Convex Quadratic and Semidefinite Programming Relaxations in Scheduling

Encyclopedia browser ?
Full browser ?