Approximation Algorithms

Approximation algorithms solve NP-hard optimization problems in polynomial time while guaranteeing a solution provably within a fixed factor of the optimum, giving rigorous trade-offs between solution quality and tractability.

Definition

An approximation algorithm for an optimization problem is a polynomial-time algorithm that returns a feasible solution whose objective value is guaranteed to be within a proven multiplicative factor — the approximation ratio — of the optimal value.

Scope

This topic covers polynomial-time algorithms that return near-optimal solutions to hard optimization problems, the approximation ratio that measures their quality, and the principal design techniques: greedy and local-search heuristics with provable bounds, linear-programming relaxation and rounding, and the primal-dual method. It also covers approximation schemes (PTAS and FPTAS) and the existence of inapproximability results that limit how well some problems can be approximated.

Core questions

• How is the quality of an approximate solution measured by an approximation ratio?
• How do LP relaxation and rounding turn a fractional optimum into a bounded integer solution?
• How do greedy and local-search methods yield provable approximation guarantees?
• What are polynomial-time approximation schemes, and which problems admit them?
• Why can some problems be approximated arbitrarily well while others cannot be approximated at all?

Key concepts

• approximation ratio
• NP-hard optimization
• greedy approximation
• local search
• LP relaxation and rounding
• primal-dual method
• PTAS and FPTAS
• inapproximability

Key theories

Approximation ratio

The approximation ratio bounds how far an algorithm's solution can be from optimal in the worst case; a c-approximation guarantees a solution within a factor c of the optimum, providing a rigorous quality certificate for an efficient algorithm.

LP relaxation and rounding

Many approximation algorithms relax an integer program to a linear program, solve it efficiently, and round the fractional solution to an integral one while bounding the loss, yielding provable ratios via the primal-dual or rounding frameworks.

Clinical relevance

Approximation algorithms make intractable optimization usable in practice: bounded-ratio methods for set cover, vertex cover, facility location, scheduling, and the traveling salesman problem guide real systems in logistics, network design, and operations research, providing solutions with quality guarantees rather than unverified heuristics.

History

The field began in the 1970s, with Johnson's analysis of approximation ratios for problems such as set cover and bin packing and Christofides' 1976 algorithm for the metric traveling salesman problem. Linear-programming and primal-dual techniques matured in the 1980s and 1990s, and probabilistically checkable proofs later established strong inapproximability results, all consolidated in textbooks by Vazirani and by Williamson and Shmoys.

Key figures

• Vijay Vazirani
• David Williamson
• David Shmoys
• David Johnson
• László Lovász

Seminal works

• vazirani2001
• williamson2011
• cormen2009

Frequently asked questions

What does a 2-approximation algorithm guarantee?

For a minimization problem, a 2-approximation always returns a solution whose cost is at most twice the optimal cost (and at least optimal for a maximization problem, within a factor of one-half). The guarantee holds for every input, no matter how adversarial.

Can every NP-hard problem be approximated well?

No. Some problems admit approximation schemes that get arbitrarily close to optimal, others have a best-possible constant ratio, and some cannot be approximated within any reasonable factor unless P equals NP. Inapproximability results establish these limits formally.