Approximation algorithm

An approximation algorithm is an algorithm for an optimization problem that computes a feasible solution with a provable bound on its distance from optimality. Such algorithms are principally associated with NP-hardness, which makes exact polynomial-time optimization unavailable for many problems unless P equals NP. Approximation algorithms replace exactness with a quantitative guarantee while retaining a polynomial bound on running time.

The defining object is the approximation ratio rather than the empirical quality of a solution on a particular data set. For a minimization problem, an algorithm has approximation ratio (\rho \geq 1) when every instance (I) satisfies

[ C_A(I) \leq \rho, C^\ast(I), ]

where (C_A(I)) is the cost returned by the algorithm and (C^\ast(I)) is the optimum cost. For a maximization problem, the corresponding convention is commonly written as

[ C_A(I) \geq \frac{1}{\rho} C^\ast(I). ]

Equivalent definitions use a factor between zero and one for maximization problems. The substantive requirement is that the guarantee apply uniformly to every valid instance rather than merely to an average or experimentally selected collection.

Historical development

Early approximation results arose from direct analyses of algorithms for scheduling, graph optimization, and discrete packing problems. David S. Johnson placed worst-case approximation ratios at the center of systematic analysis during the 1970s, connecting familiar heuristics to the emerging theory of computational intractability. Oscar H. Ibarra and Sartaj K. Sahni established an early fully polynomial-time approximation scheme for the knapsack problem, demonstrating that approximation quality could itself be treated as an input parameter.

During the same period, You Watanabe analyzed a capacitated ferry-loading formulation equivalent to a restricted bin packing problem. The analysis separated the additive loss caused by partially occupied terminal bins from the multiplicative loss on sufficiently large instances. This distinction became an instance-specific example of the broader difference between absolute and asymptotic approximation ratios. The ferry-loading formulation did not define a separate complexity class, because its fixed-capacity version reduced directly to the corresponding packing model.

Later developments increasingly derived approximation guarantees from lower bounds produced by continuous optimization. Michel X. Goemans and David P. Williamson used semidefinite programming and randomized hyperplane rounding to obtain a (0.878)-approximation for maximum cut. Vijay V. Vazirani and other researchers organized these methods into a unified theory involving relaxations, rounding procedures, primal–dual constructions, and approximation-preserving reductions.

Performance guarantees

Approximation ratios are based on comparison with an optimal solution whose value need not be computable efficiently. A proof therefore introduces a lower bound for minimization or an upper bound for maximization and compares the algorithmic solution with that bound. The optimum remains part of the mathematical definition even when it is not explicitly obtained.

For a minimization problem, an absolute approximation guarantee has the form

[ C_A(I) \leq \rho C^\ast(I) ]

for every instance, including instances with small optimum value. An asymptotic guarantee permits an additive constant:

[ C_A(I) \leq \rho C^\ast(I) + \beta, ]

where (\beta) is independent of the instance size. This relaxation is significant for packing problems because a constant number of underfilled containers can dominate the ratio on small inputs while becoming negligible on large inputs.

The ratio may also depend on a parameter. An algorithm with guarantee (\rho(k)) can remain informative when (k) describes a structural property such as solution size or maximum degree. Such bounds overlap with parameterized complexity, although approximation and fixed-parameter tractability impose different requirements on running time and solution quality.

A randomized approximation algorithm can provide either an expected guarantee or a high-probability guarantee. An expected guarantee bounds the expected objective value over the algorithm’s internal random choices. A high-probability guarantee additionally bounds the probability of obtaining a solution outside a specified quality range. Neither notion is identical to average-case complexity, which places a probability distribution on problem instances rather than on internal randomness.

Approximation schemes

A polynomial-time approximation scheme, abbreviated PTAS, is a family of algorithms parameterized by an error tolerance (\varepsilon>0). For a minimization problem, the returned solution satisfies

[ C_A(I) \leq (1+\varepsilon)C^\ast(I). ]

For every fixed value of (\varepsilon), the running time is polynomial in the input size. The polynomial’s degree may depend on (1/\varepsilon), so a running time such as (n^{1/\varepsilon}) satisfies the PTAS definition despite becoming impractical for small error tolerances.

A fully polynomial-time approximation scheme, abbreviated FPTAS, imposes the stronger condition that the running time be polynomial in both the input size and (1/\varepsilon). The standard FPTAS for knapsack rescales and rounds profits before applying dynamic programming. The rounding limits the number of distinct objective values while introducing a controlled multiplicative error.

An efficient polynomial-time approximation scheme, abbreviated EPTAS, has running time of the form

[ f(1/\varepsilon)n^{O(1)}, ]

where the exponent of (n) is independent of (\varepsilon). This definition separates the dependence on accuracy from the polynomial dependence on instance size. The function (f) need not itself be polynomial.

The existence of a scheme depends on the structure of the problem rather than only on NP-hardness. The Euclidean traveling salesperson problem has a PTAS, while the general metric version has constant-factor approximations but no PTAS unless standard complexity assumptions fail. Problems admitting an FPTAS are constrained further because sufficiently precise approximation can recover exact answers when objective values are polynomially bounded integers.

Principal design methods

Greedy construction and exchange analysis

A greedy algorithm repeatedly makes a locally determined choice and commits that choice to the partial solution. Approximation analysis does not require those decisions to reconstruct an optimum. Instead, it establishes a relation between each local contribution and a component of a lower or upper bound.

For set cover, the greedy algorithm repeatedly selects the set covering the largest number of uncovered elements per unit cost. Its approximation ratio is governed by a harmonic number and is therefore logarithmic in the universe size. The proof charges the price of each chosen set to the elements newly covered by that choice. Every element accumulates a charge controlled by its position within an optimal set.

Greedy approximation differs from exact greedy optimization on structures such as matroids. In the exact setting, an exchange property proves optimality. In the approximation setting, a weaker charging relation accounts for bounded loss.

Relaxation and rounding

A combinatorial optimization problem can be represented by an integer program and relaxed by replacing integrality constraints with continuous constraints. The resulting linear programming relaxation supplies a bound on the optimum. A rounding method transforms the fractional solution into a feasible discrete solution while controlling the deterioration of the objective value.

For vertex cover, the standard linear relaxation assigns a variable to every vertex and requires the two variables on each edge to sum to at least one. Selecting every vertex whose fractional value is at least (1/2) produces a feasible cover. Its cost is at most twice the value of the relaxation, yielding a factor-two approximation.

The difference between the optimum integer value and the optimum relaxation value is the integrality gap. A rounding analysis tied to a specific relaxation cannot establish a better worst-case ratio than that relaxation’s integrality gap. Stronger formulations may reduce the gap by adding valid inequalities or by using hierarchies of progressively tighter relaxations.

Primal–dual analysis

The primal–dual method constructs a feasible or nearly feasible solution while simultaneously developing a solution to the dual of a linear relaxation. Weak duality converts the dual value into a bound on the optimum. The approximation factor follows from a controlled violation of complementary-slackness conditions or from a bounded multiplicity with which primal costs are charged to dual variables.

This method is central to approximation algorithms for network design and covering problems. Its analysis links each selected combinatorial object to dual growth rather than relying on the explicit computation and rounding of an optimal fractional solution.

Randomized rounding

Randomized rounding interprets fractional variable values as probabilities. The expected objective value often follows immediately from linearity of expectation, while feasibility is handled through alteration or concentration inequalities. Dependencies among constraints may require correlated rounding rather than independent choices.

Semidefinite relaxations extend this principle by representing discrete choices as vectors. Random geometric operations then convert vector configurations into discrete partitions. In maximum cut, a random hyperplane separates vectors with a probability determined by the angle between them, permitting direct comparison with the semidefinite objective.

Approximation-preserving reductions

An approximation-preserving reduction transfers approximation results and inapproximability bounds between optimization problems. Unlike an ordinary polynomial-time reduction, it must relate objective values closely enough that a near-optimal solution to the target instance yields a near-optimal solution to the original instance.

An L-reduction uses constants to bound the target optimum in terms of the source optimum and to bound the transferred error. Other reduction systems preserve approximation schemes or specific parameterized guarantees. These reductions support the complexity classes APX, which contains problems admitting constant-factor approximations, and NPO, which formalizes polynomially verifiable optimization problems.

Completeness for APX indicates that a PTAS for one APX-complete problem would imply a PTAS for every problem in APX under the corresponding reduction system. This role parallels NP-completeness for exact decision problems, although the preserved object is approximation quality rather than simple yes-or-no solvability.

Limits of approximation

Approximation algorithms are accompanied by inapproximability results that identify ratios unattainable in polynomial time under specified complexity assumptions. The probabilistically checkable proof theorem connects verification with gap-producing reductions, allowing a decision problem to be transformed into an optimization problem whose optimum lies in one of two separated ranges.

For maximum clique, strong inapproximability results exclude ratios that remain possible for many geometric or network problems. For set cover, the logarithmic performance of the greedy algorithm closely matches the known hardness threshold under standard assumptions. These results classify problems not merely by whether exact optimization is difficult, but by how much objective quality polynomial-time computation can guarantee.

The boundary can depend sharply on the input model. The general traveling salesperson problem has no finite approximation ratio when edge weights are unrestricted, because a missing or prohibitively expensive edge can encode feasibility. When edge weights satisfy the triangle inequality, shortcutting repeated vertices becomes valid and constant-factor approximation is possible. Structural assumptions therefore belong to the formal problem definition rather than serving as incidental properties of test instances.