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 ?
In part because graph partitioning is itself a key component in many divide-and-conquer-based algorithms, we will also be able to use the flow result to design the first polynomial-time approximation algorithms for a wide variety of other well-known NP-hard optimization problems.
Adaptive Approximation Algorithms for Hole Healing in Hybrid Wireless Sensor Networks," 2013 Proceedings IEEE INFOCOM International Workshop on Wireless Network Measurments and Experiments (WiNMeE).
For NP-hard problems, the research focuses on developing polynomial time approximation algorithms.
The problem of cycle partition is an important tool for the design of approximation algorithms for different variants of the traveling salesman problem [6, 8, 9, 19].
For example, is the rank reduction problem computationally hard and, if so, does it admit approximation algorithms with good approximation guarantees (as is the case for graphical matroids)?
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].
However, the existing approximation algorithms for constructing an MST, cannot fully utilize the topology information of data centers with densely connected networks to refine the muticast protocols.
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.
The package provides very fast approximation algorithms by using FFT's, but the geometry is limited to the rectangle.
Approximation algorithms that run in almost linear time exist, but they are more complicated, and use for example, principal components rather than the rotating calipers [63], [64].
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.