Approximation Algorithms

Abstract

Once Cook and Karp had shown in the early 1970s that hundreds of practical optimisation problems are NP-hard, the question changed from “how do we solve this exactly?” to “how close can we get, quickly, with a proof?” An approximation algorithm runs in polynomial time and guarantees an answer within a stated factor of the optimum. Ronald Graham analysed the first one at Bell Labs in 1966; David Johnson named the field in 1974; Nicos Christofides’s 1.5-factor tour for the travelling salesman problem (1976) stood unbeaten for 44 years. The PCP theorem of 1992 then turned the subject inside out by proving that for many problems even approximation is hard beyond a precise threshold, and the Unique Games Conjecture of 2002 suggested that the best known algorithms for a whole class of problems may already be the best possible.

Graham’s Anomaly

In 1966 Ronald Graham, a mathematician at Bell Labs, published “Bounds for certain multiprocessing anomalies” in the Bell System Technical Journal. Its subject was a scheduling rule so simple that nobody thought it needed analysis: given a list of jobs and several identical machines, whenever a machine becomes free, give it the next job on the list. Graham showed two things. Counterintuitive “anomalies” occurred: adding a machine or shortening a job could make the whole schedule finish later. And however badly the rule behaved, the schedule it produced on m machines was never longer than 2 − 1/m times the best possible schedule.

The second result was the template for a new kind of theorem. It said nothing about typical inputs or about how well the rule did on test data. It was a guarantee, proved for every input, of how far a fast algorithm could be from an optimum that nobody knew how to compute.

The Field Gets a Name

The NP-completeness results of 1971 and 1972 (see Cook and Levin and Richard Karp) gave the question its urgency. If P ≠ NP, which almost everyone believed, then no exact polynomial-time algorithm existed for scheduling, packing, covering, routing and dozens of other problems that industry solved every day. Something had to be said about the algorithms people actually used.

David S. Johnson, then at MIT and later at Bell Labs, published “Approximation algorithms for combinatorial problems” in the Journal of Computer and System Sciences in 1974. He studied several NP-hard problems, among them set cover, in which a collection of sets must be chosen to cover every element of a universe, and showed that the obvious greedy method, always picking the set that covers the most uncovered elements, comes within a factor of about ln n of the optimum for n elements. László Lovász proved the same bound independently. Johnson’s paper also showed that problems equally hard to solve exactly could differ enormously in how well they could be approximated, which became the organising question of the field.

Some problems turned out to be approximable to any accuracy. In 1975 Oscar Ibarra and Chul Kim published, in the Journal of the ACM, a fully polynomial-time approximation scheme for the knapsack problem, which asks for the most valuable set of items that fits within a weight limit. For any ε > 0 the algorithm finds a solution within a factor 1 − ε of the optimum, in time polynomial in both the input size and 1/ε. The price of more accuracy is more time, but never exponential time.

Others turned out to resist approximation entirely. In 1976 Sartaj Sahni and Teofilo Gonzalez showed that for the general travelling salesman problem, where distances can be arbitrary, no polynomial-time algorithm can guarantee any constant factor unless P = NP.

The Salesman’s Factor 1.5

For the travelling salesman problem with distances that obey the triangle inequality, as road and air distances do, the picture was different (see The Traveling Salesman Problem). A minimum spanning tree, which can be computed quickly, is never longer than the optimal tour, and walking around it twice gives a tour at most twice optimal. In 1976 Nicos Christofides, and independently Anatoliy Serdyukov in the Soviet Union (published 1978), improved the factor to 1.5 by adding to the tree a cheapest matching on its odd-degree vertices, which yields a closed walk through every city at most half again as long as the best tour.

The 1.5 became one of the best-known numbers in theoretical computer science, because for decades nobody could beat it. In 2020 Anna Karlin, Nathan Klein and Shayan Oveis Gharan of the University of Washington posted a randomised algorithm that achieves 1.5 − ε for some ε greater than 10⁻³⁶. The improvement was of no practical use. It mattered because it showed that the 44-year-old barrier was not a fundamental limit. Practical solvers, which find optimal tours for instances with tens of thousands of cities, work by other means.

For cities in the plane the problem is easier. In 1996 Sanjeev Arora at Princeton and, independently, Joseph Mitchell at Stony Brook found approximation schemes for the Euclidean travelling salesman problem: for any fixed ε, a tour within 1 + ε of optimal in polynomial time. They shared the Gödel Prize in 2010. Arora’s scheme was later refined to run in nearly linear time.

Rounding the Relaxation

The most powerful general technique was to relax and round. Write the problem as an integer linear program, in which every decision variable must be 0 or 1; drop the integrality requirement and solve the resulting linear program, which is easy; then convert the fractional solution back into a real one and prove that the rounding loses at most a certain factor. For vertex cover, choosing every vertex whose fractional value is at least ½ gives a factor of 2.

In 1995 Michel Goemans and David Williamson applied the idea with a stronger relaxation to MAX-CUT, the problem of dividing the vertices of a graph into two groups so that as many edges as possible run between them. They relaxed each vertex to a unit vector in high-dimensional space, solved the resulting semidefinite program, and then cut the vectors with a random hyperplane through the origin. The expected cut was at least about 0.878 times the maximum, compared with the factor ½ that a random split gives. Their paper, published in the Journal of the ACM, made semidefinite programming a standard tool of algorithm design.

Hardness of Approximation

For twenty years the question of how well a problem could be approximated was answered only from one side: algorithms gave upper bounds, and nobody could prove that better algorithms did not exist. The PCP theorem, proved in 1992 by Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan and Mario Szegedy, building on work by Arora and Safra, changed that (see P vs NP and Complexity Theory). It states that every proof of membership in an NP language can be rewritten so that a randomised verifier, reading only a constant number of its bits, accepts correct proofs and rejects incorrect ones with high probability. Read as a statement about optimisation, it says that for some constraint satisfaction problems, telling an instance that is fully satisfiable from one in which only a fraction of the constraints can be satisfied is itself NP-hard. Approximation within that fraction is therefore NP-hard too. The PCP work was recognised with the Gödel Prize in 2001.

The results that followed were often exact. In 1998 Uriel Feige proved that set cover cannot be approximated within (1 − o(1)) ln n unless NP has slightly superpolynomial algorithms, so that Johnson’s and Lovász’s greedy algorithm of 1974 was essentially optimal. Johan Håstad’s “Some optimal inapproximability results” (Journal of the ACM, 2001) showed that for MAX-3SAT, a random assignment’s 7/8 of the clauses cannot be improved by any polynomial-time algorithm unless P = NP: the trivial algorithm is the best possible. Håstad received the 2011 Gödel Prize for it.

The Unique Games Conjecture

Many problems were left with a gap between the best algorithm and the best hardness result. In 2002 Subhash Khot, then a graduate student at Princeton, proposed the Unique Games Conjecture: that a particular kind of constraint satisfaction problem, in which each constraint on two variables allows exactly one value of the second for each value of the first, is hard to approximate in a strong sense. If the conjecture holds, many gaps close at once. In 2004 Khot, Guy Kindler, Elchanan Mossel and Ryan O’Donnell showed that under it, and under a probabilistic conjecture later proved, MAX-CUT is NP-hard to approximate beyond the Goemans-Williamson factor of about 0.878. Vertex cover would be hard to approximate beyond factor 2, the result of the simple rounding algorithm. Khot received the Nevanlinna Prize in 2014, largely for the conjecture.

Whether the conjecture is true remains open. If it is, the best algorithms for a large class of problems are already known, and most of them are relaxations followed by rounding, the method of the 1970s carried out with semidefinite programs.

Dead End: The Guarantee as a Product

Approximation guarantees are worst-case statements, and the worst case is often far from the instances that matter. Christofides’s 1.5 tours were outperformed in practice from the start by heuristics with no guarantee at all, such as the Lin-Kernighan local search of 1973, and by exact branch-and-cut solvers. Many approximation schemes, including the first Euclidean TSP schemes, are too slow to run for any reasonable ε. Practitioners rarely choose an algorithm for its approximation ratio. The field’s influence on practice came instead through its techniques, linear and semidefinite relaxations, randomised rounding and primal-dual methods, which also give a computable bound on how far a particular answer is from optimal.