Approximation, heuristics, and randomisation
When exact solutions are too expensive, algorithms can still find answers that are provably close, usually good, or correct with high probability.
Approximation algorithms
An approximation algorithm runs in polynomial time and guarantees a solution within a known factor of optimal. A 2-approximation for a minimisation problem never returns more than twice the optimal cost. For vertex cover, repeatedly picking any uncovered edge and adding both endpoints gives a 2-approximation, since any cover must contain at least one endpoint of each picked edge.
Approximating the travelling salesperson
For TSP with distances obeying the triangle inequality, building a minimum spanning tree and walking around it, skipping repeated cities, gives a tour at most twice optimal. Christofides' 1976 algorithm improves the guarantee to 1.5. Without the triangle inequality, no constant-factor approximation exists unless P equals NP, showing that guarantees depend on structure.
Approximation schemes and limits
Some problems allow any accuracy: a polynomial-time approximation scheme (PTAS) achieves within (1 + epsilon) of optimal for any epsilon > 0, with running time growing as epsilon shrinks. Knapsack has a fully polynomial scheme based on rounding values. Others resist approximation: results such as the PCP theorem show that some problems cannot be approximated beyond certain factors unless P equals NP.
Local search and metaheuristics
Local search starts from a solution and repeatedly makes small improving changes, such as swapping two edges of a TSP tour (2-opt), until no improvement is possible: a local optimum. Simulated annealing sometimes accepts worse moves, with decreasing probability, to escape local optima. Genetic algorithms and tabu search are other metaheuristics. They offer no guarantees but often find excellent solutions.
Randomised algorithms
Randomised algorithms use random choices. Las Vegas algorithms, such as randomised quicksort, always give correct answers, with random running time. Monte Carlo algorithms run in bounded time but may err with small probability, which can be reduced by repetition. Randomisation often simplifies algorithms and defeats inputs designed to trigger worst cases.
Randomised examples
The Miller-Rabin primality test checks whether a large number is prime; each round wrongly passes a composite with probability at most 1/4, so 40 rounds make the error chance below 10^-24. It is used to generate cryptographic keys. Karger's algorithm finds minimum cuts by randomly contracting edges. Random sampling and sketches, such as HyperLogLog, estimate counts in huge data streams using tiny memory.
Choosing an approach
For a hard optimisation problem, first check whether inputs are small enough for exact methods or have special structure. If a quality guarantee matters, look for an approximation algorithm. For large practical instances, combine good heuristics with local search, or hand the problem to a mature solver. Measure results on real data, and compare against lower bounds to know how close you are.
Worked example
Vertex cover 2-approximation on the path graph 1-2-3-4-5. Pick edge 1-2: add 1 and 2. Edges 2-3 is now covered; pick uncovered edge 3-4: add 3 and 4. Edge 4-5 is covered. The result {1, 2, 3, 4} has size 4. The optimum is {2, 4}, size 2, so the approximation is exactly twice optimal here, matching its worst-case guarantee.
Key takeaways
Approximation algorithms guarantee solutions within a factor of optimal in polynomial time; picking both endpoints of uncovered edges gives a 2-approximate vertex cover. Metric TSP has a 2-approximation via MSTs and Christofides' 1.5-approximation (1976); general TSP has none unless P equals NP. Some problems allow approximation schemes; others provably resist approximation. Local search, simulated annealing, and genetic algorithms find good solutions without guarantees. Las Vegas algorithms are always correct; Monte Carlo algorithms may err with small, reducible probability, as in Miller-Rabin primality testing. Match the method to input size, structure, and required guarantees.
Flashcard
Polynomial time with a quality guarantee
Check your understanding
What does it mean that an algorithm is a 2-approximation for a minimisation problem?