Approximation algorithm

An approximation algorithm runs in polynomial time and returns a feasible solution whose value is guaranteed to be within a specified factor or additive bound of optimal.

Approximation ratio: A bound comparing an algorithm’s solution value with the value of an optimal solution. It expresses the multiplicative guarantee that many approximation algorithms provide.
Combinatorial optimization: Optimization over a finite set of discrete choices, such as subsets, orderings, or graph structures. Approximation algorithms target discrete optimization problems whose exact solutions may be computationally difficult.
Vertex cover: A set of vertices in a graph that touches every edge. A simple maximal-matching method gives a factor-two approximation for minimum vertex cover.
Exact algorithm: An algorithm that always returns an optimal solution rather than an approximation. It provides the ideal benchmark, though exact methods can be too slow on hard instances.
Polynomial-time approximation scheme: An algorithmic scheme that, for each fixed error tolerance, produces a solution within that tolerance of optimal in polynomial time. It offers increasingly accurate approximations at the cost of greater running time.
NP-hardness: A property of problems at least as hard as every problem in NP under polynomial-time reductions. It explains why efficient approximation can matter when exact optimization is impractical.
Set cover: The problem of choosing the fewest sets whose union contains every element of a universe. A greedy choice achieves a logarithmic-factor guarantee and illustrates diminishing returns.
Heuristic: A practical problem-solving method that seeks good solutions without necessarily proving their quality. Unlike approximation algorithms, heuristics need not provide a formal bound on solution quality.
Fully polynomial-time approximation scheme: A polynomial-time approximation scheme whose running time is also polynomial in the inverse error tolerance. It strengthens a scheme’s efficiency by controlling its dependence on requested accuracy.
Objective function: A function assigning a value to each candidate solution in an optimization problem. Approximation quality is measured against the objective’s optimal value.

Linked from 15 pages