Advanced Algorithms · Lecture Notes
Chapter 6: Approximation Algorithms
A freight company plans the routes of vehicles that will visit hundreds of addresses every morning. A factory assigns jobs to machines at the start of the day. A network administrator wants to place enough monitors to watch every link. For all of these problems, every known algorithm that finds the best solution takes exponential time as the input grows, yet the decision has to be made in seconds. Approximation algorithms offer a middle way. They give up on the optimal solution, but they prove a bound on how much worse than optimal their answer can be. The notes first introduce the approximation ratio and what separates an approximation algorithm from a heuristic. They then treat, for the traveling salesman problem, the nearest-neighbor heuristic, the 2-approximation based on a minimum spanning tree, and 2-opt local search. For machine scheduling they cover list scheduling and the longest-processing-time-first rule. For vertex cover they present the edge-picking 2-approximation and the reduction from 3-SAT, and for the knapsack problem the ratio-ordered greedy rule and an approximation scheme. The last section covers power iteration, a typical example of numerical convergence. Every algorithm comes with Java code, a step-by-step trace, a proof of its ratio, and examples showing that the ratio is tight.
Learning outcomes
- Concepts
- Define an approximation algorithm, the approximation ratio, and approximation schemes (PTAS, FPTAS); distinguish an approximation algorithm from heuristic and metaheuristic methods.
- Traveling salesman
- Apply the nearest-neighbor heuristic, the 2-approximation based on a minimum spanning tree for metric TSP, and 2-opt local search step by step; explain why general TSP has no constant-ratio approximation.
- Scheduling and covering
- Trace list scheduling, the longest-processing-time-first rule, and the vertex cover 2-approximation in Java; prove their ratios and construct tight examples; explain the reduction from 3-SAT to vertex cover.
- Numerical convergence
- Compute the dominant eigenvalue and eigenvector with power iteration; show how the convergence rate depends on the ratio |λ2/λ1|.
6.1Approximation algorithms
Most of the algorithms studied so far find the best solution to a problem. A sorting algorithm sorts the array exactly, and a shortest-path algorithm really returns the shortest path. All of these run in polynomial time: when the input doubles, the running time grows by a constant factor. Yet for many optimization problems met in practice no such algorithm is known. For these problems the only known way to find the best solution is to try a very large fraction of the possible solutions, and the number of solutions grows exponentially or factorially with the input.
6.1.1Why exact solutions are expensive
The traveling salesman problem (TSP), vertex cover, machine scheduling, and the knapsack problem are problems of this kind. All four are NP-hard. A brief reminder of the complexity classes is useful. P is the class of decision problems solvable in polynomial time. NP is the class of decision problems for which the correctness of a proposed solution can be checked in polynomial time. A problem is NP-hard if every problem in NP reduces to it in polynomial time; if it is both NP-hard and in NP, it is NP-complete. Whether P = NP is unknown, but the common belief is that they differ. If P ≠ NP, no NP-hard problem has an exact polynomial-time algorithm.
The practical meaning of this result is clear: one should not expect a method that guarantees the best route for a hundred cities, or the best schedule for a thousand jobs, in reasonable time. Three options remain. One can settle for small inputs and accept exponential time; branch and bound and dynamic programming reduce this time but do not eliminate it. One can use a heuristic that is fast but promises nothing. The third option is the subject of these notes: an algorithm that runs in polynomial time and whose result is proven to be within a bounded distance of the optimum.
An approximation algorithm for an optimization problem is an algorithm that runs in polynomial time and, on every input, produces a feasible solution that is within a provable ratio of the optimal solution.
All three parts of the definition matter. The algorithm runs in polynomial time; otherwise it would be no different from searching for an exact solution. The solution it produces is feasible, that is, it satisfies all the constraints of the problem: the tour visits every city, the schedule assigns every job to a machine, the cover covers every edge. Finally, the quality of the solution lies within a proven bound for every input. Doing well on a few trials is not enough. The algorithm must not exceed this bound even on the worst input.
This is a trade-off. We give up a little optimality, and in return we obtain a guarantee on both efficiency and solution quality. When computing resources, that is, time and memory, are limited, this trade-off is often the most sensible choice. Moreover, the proven ratio is a worst-case bound. On inputs met in practice, the solutions found by approximation algorithms are usually much closer to the optimum than this bound.
6.1.2The balance-scale analogy
Suppose the left pan of a two-pan balance holds a load of 37 kilograms. The weights available for the right pan are 20, 10, 5, and 1 kilograms, and each can be used only once. These weights cannot balance 37 kilograms exactly: even all of them together come to only 36 kilograms. The closest balance achievable is 36 kilograms, and the difference of 1 kilogram is about 2.7% of the load.
Figure 6.1 shows this situation. The idea the analogy carries is this: instead of searching for exact balance, that is, the optimum, we accept a balance that is set up quickly and whose error is bounded. An approximation algorithm does the same. The solution it finds may not be the best, but the largest possible gap is known in advance. If the difference on the balance never exceeds 3% of the load, we can speak of an "error of at most 3%". For approximation algorithms this bound is expressed as a ratio.
6.1.3The approximation ratio
For a given input, let C be the cost of the solution the algorithm finds and C* the cost of the best (optimal) solution. For a minimization problem C ≥ C*; for a maximization problem C ≤ C*. To compare the two cases with a single measure, we divide the larger value by the smaller one.
An algorithm is a ρ(n)-approximation algorithm if, for every input of size n,
max( C / C*, C* / C ) ≤ ρ(n)
holds. We call ρ(n) the approximation ratio of the algorithm. The ratio is always ρ ≥ 1; if ρ = 1, the algorithm finds the optimal solution.
The max in the definition combines the two cases. For minimization, C ≥ C*, so the larger ratio is C / C* and the condition takes the form C ≤ ρ · C*. The cost the algorithm finds is at most ρ times the best cost. For example, a 2-approximation vertex cover algorithm picks at most twice as many vertices as the smallest cover. For maximization, C ≤ C*, so the larger ratio is C* / C and the condition becomes C ≥ C* / ρ. The value the algorithm finds is at least a 1/ρ fraction of the best value. For example, a 2-approximation knapsack algorithm guarantees at least half of the best value.
Figure 6.2 shows the two cases on a number line. For minimization the interval in which C can lie is [C*, ρ · C*], and for maximization it is [C* / ρ, C*]. The example in the figure takes C* = 20 and ρ = 2. If a minimization algorithm finds 30, the ratio for this input is 30 / 20 = 1.5. If a maximization algorithm finds 15, the ratio is 20 / 15 ≈ 1.33. Both are within the bound of 2.
In a minimization problem the algorithm finds a solution of cost 30, and the cost of the best solution is 20. For this input the ratio is C / C* = 30 / 20 = 1.5. If the algorithm is a 2-approximation, this result is within the expected bound, because 30 ≤ 2 · 20 = 40.
We can also look from the other direction. If a 2-approximation algorithm found 30, what can be said about the best cost? From the inequality C ≤ 2 · C* we get C* ≥ 15. Also, the best solution cannot be worse than the one found: C* ≤ 30. So the best cost lies between 15 and 30. The approximation ratio also yields a lower bound on the optimum without knowing it.
Writing the ratio as a function of n is deliberate. Some algorithms have a constant ratio: 2 for vertex cover, 1.5 for metric TSP. For others it grows with the input: the ratio of the nearest-neighbor heuristic on metric TSP is Θ(log n). A constant ratio is a much stronger guarantee. However large the input gets, the algorithm never strays from the optimum by more than a constant factor.
Writing the ratio upside down. For minimization the condition is C ≤ ρ · C*, for maximization C ≥ C* / ρ. Writing C ≥ ρ · C* for maximization would demand that the algorithm find a value better than the optimum, which is impossible. In both kinds of problem, ρ is at least 1. Some sources use a ratio below 1 for maximization (“at least 0.5 of the optimum”), but these notes, like the slides, always write ρ ≥ 1.
6.1.4Approximation algorithms, heuristics, and approximation schemes
The methods that can be applied to a hard optimization problem can be ranked by the guarantee they give. Table 6.1 summarizes this ranking.
| Method | Guarantee | Example |
|---|---|---|
| Exact algorithm | Best solution; exponential time on NP-hard problems | Brute-force TSP: (n − 1)!/2 tours |
| Approximation algorithm | Polynomial time and a provable ratio ρ | Vertex cover: ρ = 2 |
| PTAS | Ratio (1 + ε) for every fixed ε > 0; time polynomial in n, possibly exponential in 1/ε | Euclidean TSP (Arora, 1998) |
| FPTAS | Ratio (1 + ε); time polynomial in both n and 1/ε | Knapsack: O(n3/ε) |
| Heuristic | No guarantee; usually good in practice | Nearest neighbor, 2-opt |
| Metaheuristic | No guarantee; a search framework independent of the problem | Genetic algorithm, ant colony |
An exact algorithm gives the strongest guarantee, but on NP-hard problems its price is exponential time. An approximation algorithm stays in polynomial time and secures its quality with a ratio. For some problems the user chooses the desired accuracy with a number ε, and the algorithm returns a solution with ratio (1 + ε). Such a family of algorithms is called an approximation scheme.
A family of algorithms that gives a (1 + ε)-approximation for every fixed ε > 0 and whose running time is polynomial in n is called a polynomial-time approximation scheme (PTAS). If the running time is also polynomial in 1/ε, the family is called a fully polynomial-time approximation scheme (FPTAS).
The difference between the two schemes looks subtle at first, but in practice it is large. A PTAS with running time O(n1/ε) is polynomial for every fixed ε. Yet choosing ε = 0.1 makes the time n10, which is unusable even on an input of a hundred elements. For an FPTAS with running time O(n3/ε), on the other hand, ε = 0.1 multiplies the time by only ten. The knapsack problem has an FPTAS. Euclidean TSP for points in the plane has a PTAS; Arora and Mitchell showed this independently of each other.
The methods in the lower part of the table give no guarantee. A heuristic produces a good solution quickly with a problem-specific rule of thumb. Nearest neighbor and 2-opt are well-known TSP heuristics. A metaheuristic is a general search framework that is not tied to a particular problem; simulated annealing, genetic algorithms, and ant colony optimization belong to this group. These methods often give very good results in practice, but how far they can stray from the optimum in the worst case is unknown.
6.1.5Applications and techniques
The problems that approximation algorithms address are part of everyday life. The traveling salesman problem appears in parcel delivery and in the order of drilling holes on circuit boards. The knapsack problem is used in budget and load planning, and job scheduling in machine and processor planning. Vertex cover places the fewest monitoring points in a network. Numerical methods that converge to the eigenvalues of large matrices by iteration are also mentioned under the same heading; Google's PageRank computation is the best-known example.
The approximation techniques applied to these problems come down to a few main ideas:
- Simplification: a simpler version of the problem is solved and its result is adapted to the original problem. The linear programming relaxation (LP relaxation), which drops the integrality constraint, and the minimum spanning tree, which gives a lower bound for TSP, are of this kind.
- Greedy choice: at each step the option that looks best at that moment is taken. Nearest neighbor, longest processing time first, and ratio-ordered knapsack are examples.
- Local search: the current solution is improved by small changes; the search stops when no better neighboring solution remains. 2-opt is an example.
- Primal–dual method: the primal and dual solutions of a linear program are grown together. It is often used for covering problems.
- Randomization: random rounding or sampling gives a ratio guarantee in expectation.
- Metaheuristics: simulated annealing, genetic algorithms, ant colony optimization. They give no guarantee, but they are flexible and powerful.
These techniques have one thing in common. Almost every ratio proof builds a lower bound on the unknown value of the optimal solution. The best tour is at least as long as a minimum spanning tree; the best schedule takes at least as long as the longest job; the smallest cover contains at least as many vertices as there are edges in a matching. The result of the algorithm is compared with this lower bound. In this way the ratio is proved without ever computing the optimal solution. All the ratio proofs in these notes follow the same pattern.
6.2The traveling salesman problem
The traveling salesman problem is the most studied problem for approximation algorithms. Its definition fits in one sentence, but finding the best solution is surprisingly hard. This section first defines the problem and computes the cost of an exact solution. It then examines two approximate methods: the nearest-neighbor heuristic and the 2-approximation based on a minimum spanning tree.
6.2.1Problem definition
Traveling salesman problem (TSP): given n cities and the distance dij between every pair of cities i, j, find, among all tours that visit every city exactly once and return to the starting city, the one with the smallest total distance. If dij = dji, the problem is called symmetric TSP.
TSP is an optimization problem: the goal is to minimize the total distance. It is also a combinatorial problem, because a solution is the order in which the cities are visited, that is, a permutation. In graph terms, symmetric TSP seeks the lightest Hamiltonian cycle in a complete graph with weighted edges. A Hamiltonian cycle passes through every vertex exactly once and returns to the start.
The problem is often confused with the shortest-path problem. The shortest path between two cities is found in polynomial time with Dijkstra's algorithm. TSP, by contrast, asks for the shortest closed tour through all the cities and is NP-hard. Finding the best route for hundreds of cities is very hard in practice.
This section uses the five-city example from the slides. The cities are numbered 0 to 4, and the distances are given in the symmetric matrix of Table 6.2.
| d | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 10 | 15 | 20 | 25 |
| 1 | 10 | 0 | 35 | 25 | 30 |
| 2 | 15 | 35 | 0 | 30 | 35 |
| 3 | 20 | 25 | 30 | 0 | 40 |
| 4 | 25 | 30 | 35 | 40 | 0 |
The matrix is symmetric: for example d[1][3] = d[3][1] = 25. The diagonal is zero, because a city has no distance to itself. The length of a tour is the sum of the distances between consecutive cities plus the return from the last city to the first. For example, the tour 0 → 1 → 2 → 3 → 4 → 0 has length 10 + 35 + 30 + 40 + 25 = 140.
6.2.2The cost of an exact solution
The most direct exact method is to try all tours by brute force. There are n! orderings of n cities, but many of them write the same tour in different ways. Because the tour is closed, the starting city can be fixed: 0 → 1 → 3 → 2 → 4 → 0 and 1 → 3 → 2 → 4 → 0 → 1 are the same tour. This leaves (n − 1)! orders. In symmetric TSP a tour and its reverse also have the same length. So the number of distinct tours is (n − 1)!/2.
| n | (n − 1)!/2 | Time |
|---|---|---|
| 5 | 12 | instantly |
| 10 | 181,440 | ≈ 0.2 milliseconds |
| 15 | ≈ 4.4 · 1010 | ≈ 44 seconds |
| 20 | ≈ 6.1 · 1016 | ≈ 1.9 years |
| 25 | ≈ 3.1 · 1023 | ≈ 107 years |
Table 6.3 shows how fast the factorial grows. With five cities there are only 12 tours, and all of them can even be tried by hand. With ten cities the number of tours rises to 181,440; a computer finishes this in an instant. With twenty cities, even a computer that tries a billion tours per second runs for about two years. With twenty-five cities the time needed is about ten million years. Adding five cities multiplies the time by millions.
A smarter exact method is dynamic programming. The Held–Karp algorithm tabulates the values “the shortest path that starts at the origin, visits every city in the set S, and ends at j” and runs in O(n2 · 2n) time. For 25 cities this is about 2 · 1010 operations, which is far better than the factorial. Even so, both the time and the O(n · 2n) memory are exponential; at sixty cities this method also becomes unusable.
6.2.3The nearest-neighbor heuristic
The nearest-neighbor heuristic follows the rule a person would apply without looking at a map: always go to the nearest city not yet visited. Its steps are as follows:
- Choose a starting city and mark it as visited.
- From the current city, go to the nearest unvisited city. This is a greedy choice.
- Repeat the second step until all cities have been visited.
- Return from the last city to the starting city, closing the tour.
The Java code from the slides implements these steps directly:
int[] nearestNeighbor(int[][] d, int start) {
int n = d.length, total = 0, current = start;
boolean[] visited = new boolean[n];
int[] tour = new int[n + 1];
tour[0] = start; visited[start] = true;
for (int k = 1; k < n; k++) {
int nearest = -1, minDist = Integer.MAX_VALUE;
for (int j = 0; j < n; j++)
if (!visited[j] && d[current][j] < minDist) {
minDist = d[current][j]; nearest = j; }
// go to the nearest city
tour[k] = nearest; visited[nearest] = true;
total += minDist; current = nearest;
}
// return to the start
tour[n] = start; total += d[current][start];
return tour;
}The code takes the distance matrix d and the starting city start. The array visited records whether each city is already in the tour. The array tour has n + 1 cells, because the starting city appears in both the first and the last cell. current is the city where we are now, and total is the length of the path so far.
The outer loop runs from k = 1 to n − 1 and adds one city per round. The inner loop scans the row of the current city. Every city that is unvisited and closer than the smallest distance seen so far becomes the candidate nearest. Comparing with < also introduces a tie-breaking rule: if two cities are at the same distance, the one with the smaller index is chosen. When the inner loop ends, the nearest city is written into the tour, marked, its distance is added to the total, and it becomes the new current. After the outer loop, the edge returning from the last city to the start is added.
The cost analysis is short. The outer loop runs n − 1 times and the inner loop runs n times each time. The body of the inner loop takes constant time. The total time is O(n2). The extra memory is O(n) for the arrays visited and tour. Since the input itself is an n2-sized matrix, this running time is on the order of the time needed to read the input. Nothing faster can be expected.
6.2.4Code trace: five cities
Let nearestNeighbor(d, 0) be run with the matrix of Table 6.2. Initially visited[0] = true, tour = [0], and total = 0. Table 6.4 shows each step of the outer loop.
k | current | Distances scanned (unvisited cities) | nearest (minDist) | total | tour |
|---|---|---|---|---|---|
| 1 | 0 | d[0][1] = 10, d[0][2] = 15, d[0][3] = 20, d[0][4] = 25 | 1 (10) | 10 | 0, 1 |
| 2 | 1 | d[1][2] = 35, d[1][3] = 25, d[1][4] = 30 | 3 (25) | 35 | 0, 1, 3 |
| 3 | 3 | d[3][2] = 30, d[3][4] = 40 | 2 (30) | 65 | 0, 1, 3, 2 |
| 4 | 2 | d[2][4] = 35 | 4 (35) | 100 | 0, 1, 3, 2, 4 |
| return | 4 | d[4][0] = 25 | — | 125 | 0, 1, 3, 2, 4, 0 |
In the first step row 0 is scanned. Among the four candidates the smallest distance is 10, belonging to city 1. The tour becomes 0 → 1 and the total is 10. In the second step only the unvisited columns 2, 3, and 4 of row 1 are examined; column 0 is skipped because it is marked. The smallest value is 25, city 3 is chosen, and the total becomes 35. In the third step, from row 3, city 2 (30) is chosen over 4 (40); the total is 65. In the fourth step only one candidate remains: 4. The total becomes 65 + 35 = 100. Finally we return from 4 to 0 and add d[4][0] = 25.
The result is the tour 0 → 1 → 3 → 2 → 4 → 0 with length 125 (Figure 6.4). A verification script ran the same code from all five starting cities. The tour found from every start again has length 125. For example, starting from 2 gives the tour 2 → 0 → 1 → 3 → 4 → 2: 15 + 10 + 25 + 40 + 35 = 125.
6.2.5Comparison with brute force
With five cities there are (5 − 1)!/2 = 12 distinct tours. Once all of them have been tried, the result of nearest neighbor can be evaluated. Table 6.5 gives the twelve tours and their lengths.
| Tour | Length | Tour | Length |
|---|---|---|---|
| 0 → 1 → 3 → 2 → 4 → 0 | 125 | 0 → 1 → 2 → 3 → 4 → 0 | 140 |
| 0 → 1 → 3 → 4 → 2 → 0 | 125 | 0 → 1 → 2 → 4 → 3 → 0 | 140 |
| 0 → 1 → 4 → 2 → 3 → 0 | 125 | 0 → 2 → 1 → 3 → 4 → 0 | 140 |
| 0 → 1 → 4 → 3 → 2 → 0 | 125 | 0 → 2 → 1 → 4 → 3 → 0 | 140 |
| 0 → 2 → 3 → 1 → 4 → 0 | 125 | 0 → 3 → 1 → 2 → 4 → 0 | 140 |
| 0 → 2 → 4 → 1 → 3 → 0 | 125 | 0 → 3 → 2 → 1 → 4 → 0 | 140 |
The table gives two interesting results. First, half of the tours have length 125 and the other half length 140. The best length is 125, and six different tours reach this value. The tour found by nearest neighbor is one of them; that is, in this example the heuristic found the best result. This is luck and not the general case. Second, the matrix does not satisfy the triangle inequality: d[1][2] = 35, but going from 1 to 2 by way of 0 costs only d[1][0] + d[0][2] = 10 + 15 = 25. The direct path is longer than the detour. Such a matrix is called non-metric. This property is decisive for ratio guarantees.
The strengths and weaknesses of nearest neighbor can be summarized as follows. It is very simple and runs in O(n2) time. On random planar instances the tours it finds are on average about 25% above the best. It provides a good starting tour for local search. On the other hand, it has no constant approximation ratio. Rosenkrantz, Stearns, and Lewis showed that even when the triangle inequality holds, the ratio can reach the order of Θ(log n): the upper bound is O(log n), and inputs approaching this bound can be constructed.
6.2.6General TSP has no constant ratio
Nearest neighbor has no constant ratio, but perhaps a cleverer algorithm does. For general TSP, that is, with no condition at all on the distances, this hope is in vain. If P ≠ NP, there is no constant-ratio polynomial-time approximation algorithm for general TSP. The proof rests on the Hamiltonian cycle problem. Deciding whether a graph has a Hamiltonian cycle is NP-complete.
If P ≠ NP, then for no constant ρ ≥ 1 does general TSP have a polynomial-time ρ-approximation algorithm.
The proof is by contradiction. Suppose there is a polynomial-time ρ-approximation algorithm A. Let G be any graph with n vertices. From this graph we build a TSP instance as follows: the cities are the vertices of G; pairs joined by an edge in G get distance 1, and pairs not joined get distance ρn + 1. The construction takes O(n2) time.
If G has a Hamiltonian cycle, that cycle is a tour all of whose edges have length 1. The best tour has length n. The tour of A has length at most ρn. This tour cannot contain even a single heavy edge, because that edge alone would cost ρn + 1 > ρn. Hence the tour of A uses only edges of G and is a Hamiltonian cycle of G.
If G has no Hamiltonian cycle, every tour contains at least one heavy edge and has length greater than ρn. So does the tour of A.
Therefore, running A and checking whether the length of its tour exceeds ρn tells us in polynomial time whether G has a Hamiltonian cycle. Since the Hamiltonian cycle problem is NP-complete, this means P = NP, contradicting the assumption. □
The strength of the construction comes from the heavy edges: even a single heavy edge ruins the ratio. But this construction violates the triangle inequality badly: while the heavy edge u–v has length ρn + 1, the path through a common neighbor is only 2. For TSP with distances satisfying the triangle inequality the construction is invalid, and constant-ratio algorithms exist.
6.2.7MST-based 2-approximation for metric TSP
A TSP instance is called metric TSP if the inequality dij ≤ dik + dkj holds for all cities i, j, k. This inequality is called the triangle inequality: going directly between two cities is never longer than stopping at a third city on the way.
Most real-life distances are metric. Euclidean distance between points in the plane, shortest-path distances in a road network, and flight times are of this kind. Metric TSP is still NP-hard, but a constant-ratio algorithm is now possible. The simplest one is based on the minimum spanning tree (MST). A minimum spanning tree is the tree connecting all the vertices of a graph whose total weight is smallest. It is found in O(n2) or O(E log V) time with Prim's or Kruskal's algorithm.
The algorithm has three steps:
- Build a minimum spanning tree T in the complete graph of the cities.
- Traverse T depth-first from a root city. Every edge is used once going and once returning. The length of this closed walk is 2 · w(T).
- Skip the cities already seen in the walk (shortcutting). What remains is the preorder of the cities; appending the starting city at the end closes the tour.
The example in the slides has seven cities in the plane, with Euclidean distances. A verification script recovered the coordinates of the cities from the drawing in the figure: A (10, 20), B (18, 68), C (42, 86), D (50, 46), E (76, 78), F (92, 42), G (62, 10). All distances are computed from these coordinates.
If Prim's algorithm is started from A, the edges are added in this order: A–D (47.7), D–G (37.9), D–B (38.8), B–C (30.0), C–E (34.9), E–F (39.4). The total weight is w(T) = 228.8 (Figure 6.5). It is easy to see why the tree is a lower bound for the best tour. If any edge is deleted from the best tour, a path connecting all the cities remains. A path is also a spanning tree. Since the minimum spanning tree is the lightest of all spanning trees, it cannot be longer than this path. Because edge weights are nonnegative, w(T) ≤ OPT follows.
In the second step the tree is traversed depth-first from A. The traversal in the slides visits B before G among the children of D: A → D → B → C → E → F → E → C → B → D → G → D → A. Every tree edge is used twice, and the length of the walk is 2 · 228.8 = 457.6. This walk is not a valid tour, because D, B, C, and E are passed more than once.
In the third step the repeated cities are skipped. The walk is read from the left, and every city seen for the first time is written into the tour: A, D, B, C, E, F; then E, C, B, D are skipped; G is written; D and A are skipped. Appending A at the end gives the tour A → D → B → C → E → F → G → A. Its length is computed step by step in Table 6.6.
| Edge | Length | Note |
|---|---|---|
| A → D | 47.7 | tree edge |
| D → B | 38.8 | tree edge |
| B → C | 30.0 | tree edge |
| C → E | 34.9 | tree edge |
| E → F | 39.4 | tree edge |
| F → G | 43.9 | shortcut: replaces the walk F → E → C → B → D → G (181.0) |
| G → A | 53.0 | shortcut: replaces the walk G → D → A (85.6) |
| Total 287.7 | ||
The table shows that the shortcuts never lengthen the walk. The walk from F to G passes through five tree edges and costs 181.0, while the direct edge F–G is 43.9. What guarantees this is the triangle inequality: skipping an intermediate city, that is, using dij instead of dik + dkj, does not increase the length. Applying the skip repeatedly, several intermediate cities can be skipped at once.
In metric TSP, the tour built from the preorder of a minimum spanning tree is at most twice as long as the best tour: tour ≤ 2 · OPT.
The proof combines two inequalities. The first is the lower bound: deleting an edge from the best tour leaves a spanning path, this path is a spanning tree, and its weight is at least w(T). Since the weight of the deleted edge is nonnegative, w(T) ≤ OPT.
The second is the upper bound. Traversing the tree twice uses every edge exactly twice, and its length is 2 · w(T). The tour is obtained from this walk by shortcuts. Each shortcut replaces a subwalk between two cities with the direct edge. Applying the triangle inequality repeatedly, the direct edge cannot be longer than the subwalk. Hence tour ≤ 2 · w(T). Combining the two inequalities gives tour ≤ 2 · w(T) ≤ 2 · OPT. □
In the example, brute force tries all 6!/2 = 360 tours. The best tour is A → B → C → E → F → G → D → A with length 282.5. The 287.7 found by the algorithm is only about 1.02 times the best. The guarantee is 2, but the practical result is much better. The bounds in the proof can also be checked: w(T) = 228.8 ≤ 282.5 = OPT and 287.7 ≤ 457.6 = 2 · w(T).
In a depth-first traversal the algorithm does not specify the order in which the children of a vertex are visited. The traversal in the slides takes B before the other child G of D. Prim's algorithm, however, adds G to the tree before B (D–G 37.9, D–B 38.8). If the children were traversed in the order they were added to the tree, the walk would be A → D → G → D → B → C → E → F → E → C → B → D → A. The tour with shortcuts comes out as A → D → G → B → C → E → F → A. Its length is 47.7 + 37.9 + 72.8 + 30.0 + 34.9 + 39.4 + 84.9 = 347.7. This tour is noticeably longer than the one in the slides, but it is still below the bound 2 · w(T) = 457.6. The ratio is 347.7 / 282.5 ≈ 1.23. The guarantee is independent of the order of the children; the actual result is sensitive to it.
The running time of the algorithm is determined by building the tree. On the complete graph, Prim's algorithm with an array-based implementation takes O(n2). The depth-first traversal and the shortcut step are O(n). The total time is O(n2), the same order as nearest neighbor, but now there is a proven ratio.
Forgetting the triangle inequality. That the shortcut step does not lengthen the walk holds only for metric instances. In the matrix of Table 6.2, d[1][2] = 35 is greater than d[1][0] + d[0][2] = 25. In such an instance a shortcut from 1 to 2 lengthens the walk, and the bound tour ≤ 2 · OPT loses its validity. The algorithm still produces a tour, but without a guarantee.
6.2.8Christofides and other bounds
The loss of the MST-based algorithm comes from one place: every tree edge is walked twice. In 1976 Christofides replaced this double walk with a cheaper structure. The vertices of odd degree in the tree are found; their number is always even. A minimum-weight perfect matching is built among these vertices. In the union of the tree and the matching every vertex has even degree, so an Euler tour exists. An Euler tour is a closed walk that passes through every edge exactly once. Shortcutting is applied to this walk. The weight of the matching is at most OPT / 2; the total is w(T) + OPT/2 ≤ 1.5 · OPT. Because of the matching step, the running time of the algorithm is O(n3).
Christofides's bound of 1.5 could not be improved for more than forty years. In 2020 Karlin, Klein, and Oveis Gharan reduced the ratio to 3/2 − ε with a randomized algorithm; here ε is a very small constant greater than 10−36. It makes no practical difference, but it shows that 1.5 can be beaten. Table 6.7 collects the main known results for TSP.
| Case | Ratio | Note |
|---|---|---|
| General TSP | none | If P ≠ NP, there is no polynomial-time ρ-approximation for any constant ρ; one would solve the Hamiltonian cycle problem. |
| Metric TSP, MST-based | 2 | MST + preorder traversal + shortcuts; O(n2). |
| Metric TSP, Christofides | 1.5 | MST + minimum perfect matching on the odd-degree vertices + Euler tour (1976); O(n3). |
| Euclidean TSP | 1 + ε | A PTAS exists for points in the plane (Arora, Mitchell). |
| Nearest neighbor | Θ(log n) | Guarantees no constant ratio even in the metric case. |
6.3Local search: 2-opt
Nearest neighbor and the MST-based algorithm build a tour from scratch. Local search instead assumes that a tour is already in hand and improves it step by step. The starting tour can be random or can come from another heuristic.
6.3.1The idea of local search
Local search is a search method that starts from a solution and improves it by small changes. The solutions reachable from a given solution by a single change are called its neighbors. A solution none of whose neighbors is better than itself is called a local optimum.
Local search resembles a climber ascending in fog. The climber sees only the area around the current position. The climber takes whichever step leads higher and stops when no direction goes up. The place where the climber stops is a peak, but perhaps not the highest peak of the mountain. Local search likewise stops at a local optimum. This point need not be the global optimum, that is, the best of all solutions.
6.3.2The 2-opt move and its gain
Remove two edges from a tour: (a, b) and (c, d). The tour falls into two pieces. There is exactly one way to join the pieces into a tour again that differs from the old connections: connect a to c and b to d. After this connection the subpath between b … c is traversed in the opposite direction. This change is called a 2-opt move.
Whether the move shortens the tour can be told by looking at just four edges. The inner edges of the reversed subpath stay the same, because in symmetric TSP the length of an edge does not depend on its direction. Only the two edges removed and the two edges added change. The gain of the move is written as follows:
Δ = d(a, c) + d(b, d) − d(a, b) − d(c, d)
If Δ < 0, the new tour is shorter than the old one by |Δ| and the move is made. If Δ ≥ 0, the move does not shorten the tour. The gain is computed in O(1) time. The tour length is not re-summed.
In the Euclidean plane 2-opt has a geometric interpretation: two crossing edges can always be removed. Let the segments (a, b) and (c, d) cross at a point X. By the triangle inequality, d(a, c) ≤ d(a, X) + d(X, c) and d(b, d) ≤ d(b, X) + d(X, d). The sum of the right-hand sides is exactly d(a, b) + d(c, d). Hence Δ ≤ 0, and the inequality is strict unless the points are collinear. Consequently, no edge of a Euclidean tour that is a 2-opt local optimum crosses another.
Let the points be a (0, 0), b (4, 3), c (4, 0), d (0, 3), and let the tour contain the edges (a, b) and (c, d). These two edges are the diagonals of a rectangle and cross each other. Each has length √(16 + 9) = 5. The new edges (a, c) and (b, d) are the horizontal sides of the rectangle, of length 4. The gain is Δ = 4 + 4 − 5 − 5 = −2. The tour becomes 2 units shorter and the move is made.
When no pair of edges remains that would give a 2-opt move, the tour is a 2-opt local optimum. Such a tour is usually a good one, but it need not be the global optimum. To reach a better tour it may be necessary to change more than two edges at once.
6.3.3Code and cost
The Java code from the slides follows the "first improvement" strategy. It scans the tour and immediately applies the first move whose gain is negative:
void twoOpt(int[] tour, double[][] d) {
int n = tour.length;
boolean improved = true;
while (improved) {
improved = false;
for (int i = 0; i < n - 1; i++)
for (int j = i + 2; j < n; j++) {
int a = tour[i], b = tour[i + 1];
int c = tour[j], e = tour[(j + 1) % n];
double delta = d[a][c] + d[b][e]
- d[a][b] - d[c][e];
if (delta < -1e-9) { // shorter
reverse(tour, i + 1, j);
improved = true;
}
}
}
}The tour is kept in the array tour of city numbers and is closed: there is an edge from the last city to the first. The flag improved records whether at least one move was made during a scan. The outer while loop continues until a scan ends without making any move.
The inner loops run over pairs of edges. Edge i is the edge between tour[i] and tour[i + 1]; edge j is between tour[j] and tour[(j + 1) % n]. The modulo operation makes sure the last edge, the one returning from the last city to the first, is also taken into account. Starting j at i + 2 prevents the choice of two adjacent edges. Adjacent edges share an endpoint, and a 2-opt move on them does not change the tour. Still, in the case i = 0 and j = n − 1 the two edges meet at the start of the tour: e = tour[0] = a, and the gain always comes out zero. The code does not exclude this case separately; since the gain is zero, no move is made.
The gain is computed in the variable delta. The comparison is made with delta < -1e-9 rather than delta < 0. Because the distances are double, rounding errors can turn a difference that should be zero into a tiny negative number such as −10−16. Such a "phantom gain" can make the algorithm go back and forth between the same two tours forever. The small threshold prevents this.
When a move is made, reverse(tour, i + 1, j) is called. This helper method is not given in the slides; it reverses in place the elements between tour[i + 1] and tour[j], both ends included. It can be written as a loop that swaps elements from the two ends toward the middle:
void reverse(int[] t, int i, int j) {
while (i < j) {
int x = t[i]; t[i] = t[j]; t[j] = x;
i++; j--;
}
}The cost can be examined at three levels. A scan looks at about n(n − 3)/2, that is, O(n2) pairs of edges. The gain of each pair is computed in O(1). For a pair where a move is made, the reversal takes O(n). How many scans will be made is not known in advance. In the worst case the number of scans can be exponential; theoretically, bad inputs can be constructed. In practice a few dozen scans usually suffice.
6.3.4Code trace: four points
The trace in the slides works with four points: 0 (0, 0), 1 (3, 4), 2 (3, 0), and 3 (0, 4). The points are the corners of a 3 × 4 rectangle. The distances are Euclidean: the horizontal sides are 3, the vertical sides 4, and the diagonals 5 units. The starting tour is 0 → 1 → 2 → 3 → 0. This tour uses both diagonals: d(0, 1) + d(1, 2) + d(2, 3) + d(3, 0) = 5 + 4 + 5 + 4 = 18.
| Pass | i, j | a, b, c, e | delta | Result |
|---|---|---|---|---|
| 1 | 0, 2 | 0, 1, 2, 3 | 3 + 3 − 5 − 5 = −4 | move: tour = [0, 2, 1, 3], length 14 |
| 1 | 0, 3 | 0, 2, 3, 0 | 4 + 3 − 3 − 4 = 0 | adjacent edges (e = a); no move |
| 1 | 1, 3 | 2, 1, 3, 0 | 5 + 5 − 4 − 4 = 2 | no move; improved = true |
| 2 | 0, 2 | 0, 2, 1, 3 | 5 + 5 − 3 − 3 = 4 | no move |
| 2 | 0, 3 | 0, 2, 3, 0 | 4 + 3 − 3 − 4 = 0 | no move |
| 2 | 1, 3 | 2, 1, 3, 0 | 5 + 5 − 4 − 4 = 2 | no move; improved = false, the loop ends |
Table 6.8 gives the trace. Since n = 4, i ranges from 0 to 2 and j from i + 2 to 3. The valid pairs are (0, 2), (0, 3), and (1, 3). In the first pass the pair (0, 2) removes the diagonals (0, 1) and (2, 3) and proposes the edges (0, 2) and (1, 3). These are the short edges of 3 units: delta = 3 + 3 − 5 − 5 = −4. The move is made, reverse(tour, 1, 2) swaps 1 and 2, and the tour becomes [0, 2, 1, 3]. The new length is 3 + 4 + 3 + 4 = 14.
The scan continues on the same tour. For the pair (0, 3) the two edges share an endpoint (e = a) and the difference is zero. The pair (1, 3) brings the diagonals back and gives +2. Because a move was made in the first pass, the scan is repeated; in the second pass no pair gives a negative gain and the loop ends.
The result is the tour [0, 2, 1, 3] with length 14. This tour is the perimeter of the rectangle. With four points there are only three distinct tours (3!/2 = 3): the perimeter (14) and two tours using diagonals (18 and 16). In this example the 2-opt local optimum is also the global optimum.
6.3.52-opt on twenty-eight cities
A larger example shows the power of 2-opt more clearly. In the slides 28 cities are placed at random in the range 0–100 and a random starting tour is chosen. The tour edges cross each other constantly, and the length is 1269.8. A verification script read the city coordinates from the drawing in the slides and ran the same twoOpt code. All the values in the slides match this run exactly.
| Move | Gain Δ | Tour length |
|---|---|---|
| start | — | 1269.8 |
| 1 | −36.9 | 1232.9 |
| 2 | −8.9 | 1224.0 |
| 4 | −27.6 | 1187.3 |
| 8 | −32.6 | 1111.7 |
| 14 | −14.9 | 1005.2 |
| 22 | −37.0 | 852.8 |
| 32 | −11.8 | 595.9 |
| 48 (last) | −13.2 | 430.8 |
The values in Table 6.9 show two things. First, the gain of an individual move is small. The gains in the table range from 9 to 37 units; even the largest of the 48 moves (70.4) does not exceed 10% of the tour length at that moment. The first-improvement strategy does not look for large gains; it takes the first gain it finds. Second, these small gains add up. After 48 moves the tour drops to 430.8. This is about 34% of the starting length.
The final tour has no crossing edges (Figure 6.11). This is the result expected from the geometric interpretation of the 2-opt move: the edges of a Euclidean tour that is a 2-opt local optimum do not cross each other. But the absence of crossings does not mean the tour is the best. There are many tours without crossings, and their lengths differ from one another.
The strategy and the starting tour affect the result. A verification script made two more experiments. The "best improvement" strategy examines all pairs in each scan and applies the one with the largest gain. Starting from the same random tour, it stops after 23 moves and finds a local optimum of length 441.9. First improvement started from the nearest-neighbor tour (518.6), on the other hand, stops after only 10 moves and reaches 449.7. In this example the random start took longer but arrived at a better local optimum. No general rule can be drawn. The result of local search depends on the start and the strategy; in practice it is run several times from different starts and the best result is kept.
6.3.6Escaping local optima: metaheuristics
The basic problem of local search is that it gets stuck in the first local optimum. An algorithm that accepts only improving moves cannot climb out once it has fallen into a pit. Metaheuristics overcome this problem in different ways: they sometimes accept worsening moves too, they improve many solutions together at the same time, or they learn from the past.
Simulated annealing takes its name from the annealing of metals. If hot metal is cooled slowly, its atoms settle into an ordered, low-energy structure. At each step the algorithm picks a random neighbor. If the neighbor is better, the move is made. If it is worse, that is, it increases the cost by Δ > 0, the move is accepted anyway with probability e−Δ/T. Here T is a parameter called the "temperature", and it is lowered slowly. A typical setting starts with T0 = 100 and sets T ← 0.997 · T at each step.
| Temperature T | Δ / T | Acceptance probability |
|---|---|---|
| 100 | 0.05 | ≈ 0.95 |
| 10 | 0.5 | ≈ 0.61 |
| 1 | 5 | ≈ 0.0067 |
Table 6.10 shows the effect of temperature. At high temperature even worsening moves are accepted almost always, and the search roams freely over the landscape. As the temperature falls, moves become more selective. At T = 1, a move that worsens the solution by 5 units is accepted about once in 150 trials. In the end the algorithm turns into a local search that accepts almost only improving moves. The cooling rate can also be computed. The inequality 100 · 0.997k < 1 gives k > ln 100 / (−ln 0.997) ≈ 1532.8; the temperature falls below 1 in 1533 steps.
Genetic algorithms work with a population of tours. Shorter tours are selected more often, the selected tours are combined by crossover, and mutation preserves diversity. A typical setting is a population of 100 individuals, crossover with a random cut point, and a mutation probability of 0.05.
Ant colony optimization is inspired by real ants. Artificial ants that build short tours leave more pheromone on edges; later ants prefer edges with dense pheromone, and the pheromone evaporates over time.
All three methods are widely used in TSP, vehicle routing, job scheduling, and assignment problems. None of them guarantees an approximation ratio. The result is sensitive to the starting solution, the parameters, and the seed of the random number generator.
Assuming the result of a metaheuristic is exact. It is theoretically known that if the temperature is lowered slowly enough, at a logarithmic rate, simulated annealing converges in probability to the global optimum. Every cooling schedule used in practice, however, is finite and gives no guarantee. The same algorithm is run several times with different seeds and parameters, and the best result is taken. To say how close the result found is to the best, a lower bound is needed, for example the weight of the minimum spanning tree.
6.4Job scheduling
Job scheduling is the planning of jobs on given resources (workers, machines, processors) as efficiently as possible. The goal is to minimize the completion time of the jobs, or to find the best plan by criteria such as profit, lateness, and deadlines. This section separates two problems and examines in detail the one that is the subject of approximation algorithms.
6.4.1Two scheduling problems
In the machine scheduling problem there are n jobs and m identical machines. Job j has processing time pj. Each job runs on a single machine without interruption. The load of a machine is the sum of the processing times of the jobs assigned to it. The moment the last job finishes, that is, the load of the most loaded machine, is denoted Cmax. This value is called the makespan. The goal is to minimize Cmax. The problem is NP-hard for m ≥ 2; even the case m = 2 is a version of the problem of splitting the jobs into two sets with equal sums.
In the job sequencing with deadlines problem every job takes one unit of time and has a profit and a deadline. The total profit of the jobs that finish before their deadlines must be maximized. This problem is solved optimally by a greedy algorithm that takes the jobs in decreasing order of profit and places each in the latest free slot before its deadline.
6.4.2List scheduling
List scheduling takes the jobs in the given order and assigns the next job to the machine that becomes free earliest at that moment, that is, the least loaded machine. The algorithm is due to Graham (1966).
List scheduling is an online algorithm: when assigning a job it does not need to know the jobs that come later. It can therefore be used directly in settings where jobs arrive over time. The example in the slides shows this case. There are three identical machines M1, M2, and M3. J1 (length 2), J2 (length 8), and J3 (length 6) are ready at t = 0; J4 (length 3) arrives at t = 3.
| Event | Decision | Reason |
|---|---|---|
| J1 (2), t = 0 | M1, [0, 2] | All machines are idle; the first machine is chosen. |
| J2 (8), t = 0 | M2, [0, 8] | M1 is busy until t = 2. |
| J3 (6), t = 0 | M3, [0, 6] | M1 is busy until t = 2, M2 until t = 8. |
| t = 2 | M1 idle | No job is waiting; M1 stays idle until t = 3. |
| J4 (3), t = 3 | M1, [3, 6] | M1 is idle; M2 is busy until t = 8, M3 until t = 6. |
After all jobs are assigned, the makespan is 8 and belongs to M2 (Figure 6.14). This schedule is optimal, because no schedule can finish before the longest job. J2 alone takes 8 units, so the best makespan is at least 8. In general, however, list scheduling does not find the optimum; it guarantees only the ratio 2 − 1/m.
If the least loaded machine is found by scanning an array, the time is O(nm); if the machines are kept in a min-heap, it is O(n log m).
6.4.3The ratio of list scheduling
The ratio proof rests on two lower bounds for the optimal solution. One concerns the workload. The total work is Σ pj and must be spread over m machines. Even in the best schedule some machine has a load at least equal to the average: OPT ≥ Σ pj / m. The other concerns the longest job. Each job runs on one machine without interruption; the longest job alone takes max pj: OPT ≥ max pj.
If all jobs are ready at the start, list scheduling produces, whatever the order of the jobs, a schedule satisfying Cmax ≤ (2 − 1/m) · OPT.
Let j be the job that finishes last in the schedule and let it start at time sj. Then Cmax = sj + pj. At the moment j was assigned it went to the least loaded machine; so at that moment every machine had a load of at least sj. In other words, before sj all machines were busy; if a machine had been idle, j would have started earlier. This busy time comes from jobs other than j: m · sj ≤ Σ p − pj, that is, sj ≤ (Σ p − pj) / m.
Cmax = sj + pj ≤ Σ p / m + (1 − 1/m) · pj ≤ OPT + (1 − 1/m) · OPT = (2 − 1/m) · OPT
The last step uses the two lower bounds: Σ p / m ≤ OPT and pj ≤ max p ≤ OPT. □
That the ratio is tight, that is, that no better bound can be proved, is shown by an example. Let m = 2 machines and three jobs of lengths 1, 1, 2 in this order. List scheduling gives the first job to M1 and the second to M2; for the third job both machines have load 1, and the job goes to M1. The loads become 3 and 1; Cmax = 3. The best schedule puts the two short jobs on one machine and the long job on the other and finishes at 2. The ratio is 3/2 = 2 − 1/2; the bound in the theorem is reached exactly.
The example generalizes to every m: let m(m − 1) jobs of 1 unit come first, then a single job of m units. The short jobs spread evenly over the machines and each machine gets load m − 1. The long job is added to one of them: Cmax = 2m − 1. The best schedule gives the long job a machine of its own and spreads the short jobs over the remaining m − 1 machines, m each: OPT = m. The ratio is (2m − 1)/m = 2 − 1/m. For m = 3, six jobs of 1 unit and one job of 3 units give the ratio 5/3.
6.4.4Longest processing time first (LPT)
The tight examples show the same weakness: when a long job is left to the end, a single machine keeps working while the other machines have long since finished. The fix is simple: put the long jobs first. The longest processing time first (LPT) rule sorts the jobs in decreasing order of processing time and then applies list scheduling. The jobs left for the end are short; they correct the imbalance.
In the example in the slides the jobs are 2, 3, 4, 6, 2, 2 and m = 3. The total work is 19, so the best makespan is at least ⌈19/3⌉ = 7. List scheduling in the given order first distributes 2, 3, and 4 over the three machines. The job of 6 units goes to the least loaded machine, M1 with load 2, whose load becomes 8. The remaining two short jobs are added to M2 and M3. Cmax = 8. The LPT order is 6, 4, 3, 2, 2, 2. The long jobs spread over the three machines first; the short jobs are then added to the least loaded machines and the loads become 6, 6, 7. Cmax = 7, which is optimal because it equals the lower bound.
The LPT rule produces a schedule satisfying Cmax ≤ (4/3 − 1/(3m)) · OPT. Its running time is O(n log n) because of the sorting.
The outline of the proof is as follows. Suppose there is a counterexample that exceeds the bound, and take one with the fewest jobs. In this instance the job j that finishes last is the shortest job. Otherwise the jobs after j could be deleted, Cmax would not change, OPT would not increase, and a smaller counterexample would be found.
The inequality from the list scheduling proof applies here too: Cmax ≤ Σ p / m + (1 − 1/m) · pj ≤ OPT + (1 − 1/m) · pj. If pj ≤ OPT/3, the right-hand side is OPT + (1 − 1/m) · OPT/3 = (4/3 − 1/(3m)) · OPT and the bound holds. So in the counterexample pj > OPT/3. Since j is the shortest job, all jobs are longer than OPT/3. In the best schedule at most two jobs fit on a machine. In this case it can be shown directly that LPT finds the best schedule: the longest m jobs are placed one per machine, and the rest are matched so that the shortest job comes next to the longest job. A contradiction is obtained. □
The LPT bound is also tight. Let m = 3 and the jobs 5, 5, 4, 4, 3, 3, 3. LPT first makes the loads 5, 5, 4. The next 4 and two 3s bring the loads to 8, 8, 8; the last 3 raises one machine to 11. The best schedule, {5, 4}, {5, 4}, {3, 3, 3}, finishes at 9: ratio 11/9 = 4/3 − 1/9. The same pattern can be built for every m: 2m − 1, 2m − 1, …, m + 1, m + 1 and three jobs of m. A verification script checked for m = 2, 3, 4 that LPT gives 4m − 1 and the best schedule gives 3m.
LPT is not online: to sort the jobs it must know all of them in advance. In return its guarantee is much stronger. As m grows, the bound of list scheduling approaches 2 and that of LPT approaches 4/3; for m = 2 the values are 1.5 and 7/6 ≈ 1.17, for m = 4 they are 1.75 and 1.25. Machine scheduling also has a PTAS (Hochbaum and Shmoys, 1987): every ratio 1 + ε can be reached in polynomial time, but the time is exponential in 1/ε.
6.4.5LPT code and trace
The Java code in the slides writes LPT in the simplest way:
int lpt(Integer[] jobs, int m) {
Arrays.sort(jobs, Comparator.reverseOrder());
int[] load = new int[m];
for (int p : jobs) {
int k = 0; // least loaded
for (int i = 1; i < m; i++)
if (load[i] < load[k]) k = i;
load[k] += p;
}
return Arrays.stream(load).max().getAsInt();
}The first line sorts the jobs from largest to smallest with Comparator.reverseOrder(). Because this comparator works with objects, the array is of type Integer[], not int[]. The array load holds the current load of each machine and starts at zero. The loop takes each job in turn. The inner loop finds the index of the least loaded machine in k. The comparison is strictly less than (<); so if loads are equal, the machine with the smaller index is chosen. The job is added to that machine's load. Finally the largest of the loads is returned.
If the first line of the code is deleted, list scheduling remains: jobs go to the least loaded machine in the order given. This ordering is the only difference between the two algorithms. In the code the least loaded machine is found by scanning an array, which takes O(m) per job. The total time is O(n log n + nm). If the machines are kept in a heap, the time drops to O(n log n + n log m) = O(n log n).
| Step | p | load (before) | Least loaded k | load (after) |
|---|---|---|---|---|
| 1 | 6 | [0, 0, 0] | 0 (first machine on a tie) | [6, 0, 0] |
| 2 | 4 | [6, 0, 0] | 1 (load 0) | [6, 4, 0] |
| 3 | 3 | [6, 4, 0] | 2 (load 0) | [6, 4, 3] |
| 4 | 2 | [6, 4, 3] | 2 (load 3) | [6, 4, 5] |
| 5 | 2 | [6, 4, 5] | 1 (load 4) | [6, 6, 5] |
| 6 | 2 | [6, 6, 5] | 2 (load 5) | [6, 6, 7] |
Table 6.12 shows each step of the code. In the first step all loads are zero. The inner loop starts with k = 0 and does not change it, because no load is less than 0; 6 goes to the first machine. In the second and third steps the empty machines are filled in turn. In the fourth step the least loaded machine is M3 with load 3 (k = 2). In the fifth step the loads are 6, 4, 5 and the job of 2 goes to the machine with load 4. In the last step the loads are 6, 6, 5 and the last job is added to the machine with load 5. The makespan is 7. Since the lower bound is ⌈19/3⌉ = 7, this schedule is optimal.
6.5Vertex cover
Suppose every link in a campus network is to be monitored. When monitoring software is installed on a router, it sees all the lines connected to that router. On how few routers must the software be installed? This question is the classic vertex cover problem of graph theory.
6.5.1Problem definition
Let G = (V, E) be an undirected graph. A set C ⊆ V that contains at least one endpoint of every edge is called a vertex cover. An edge is covered if one of its endpoints is in the set. The minimum vertex cover problem asks for the cover with the fewest elements.
A cover can be thought of as a guard arrangement: the guard at each vertex sees the edges touching that vertex, and every edge must be seen by at least one guard. The decision version of the problem, that is, the question “is there a cover of k vertices?”, is NP-complete.
In the graph of Figure 6.18 the six-vertex set on the left is valid, but the three vertices on the right do the same job. The leftmost vertex covers two edges of the quadrilateral, the central hub covers the other two edges of the quadrilateral and the four edges leading to the right, and the inner vertex on the right covers the edges going to the three leaves. It can also be shown that fewer than three do not suffice: one edge of the quadrilateral, one edge going from the hub to the right, and one leaf edge are three edges with no common endpoint. Each needs a separate guard.
The second example in the slides has four vertices. The vertices are A, B, C, D and the edges are (A, B), (A, C), (B, C), (B, D), (C, D). The set {A, B, C} is a valid cover: every edge has at least one endpoint in the set. But it is not minimum, because {B, C} also covers all five edges. A single vertex does not suffice; for example, B does not cover the edge (A, C). The best value is 2.
6.5.2Solution approaches
The exact solution checks each of the 2n subsets in O(m) time: O(2n · m) in total. Branch and bound and linear programming speed up this search but do not remove the exponential time.
For approximate solutions two greedy ideas stand out: choosing the vertex of highest degree, and taking both endpoints of an uncovered edge at once. The first looks natural but has a weak guarantee; the second looks wasteful but guarantees the ratio 2.
The graph in Figure 6.20 is used in the trace. Its edges are (A, B), (A, C), (A, D), (A, E), (A, F), (B, C), (G, H), (G, I), (H, I), (H, K), (I, J), (J, K), (J, L). A verification script tried all subsets. The minimum cover has 5 vertices, and there are four different optimal solutions: {A, B, H, I, J}, {A, B, G, H, J}, {A, C, H, I, J}, and {A, C, G, H, J}. That fewer than five do not suffice can be seen as follows: the triangle A, B, C needs at least two vertices; so does the triangle G, H, I. The edge (J, L) also needs a vertex separate from these two triangles.
6.5.3Why is adding one endpoint not enough?
The first algorithm that comes to mind is this. Initially the cover is empty. An uncovered edge is chosen and one of its endpoints is added to the set. This step is repeated until all edges are covered. The algorithm always produces a valid cover, but nothing can be said about its quality unless a rule is given for which endpoint to add.
Figure 6.21 shows the bad case. The center m is connected to five leaves. If the algorithm chooses the leaf endpoint at every edge, the edges are covered one by one, and in the end all five leaves are chosen. Yet choosing only the center covers all the edges. On a star with n leaves the ratio of this algorithm is n, which grows without bound with the input.
The correct 2-approximation makes a small but decisive change. An uncovered edge (u, v) is chosen and both u and v are added to the set. All edges touching u or v count as covered. These steps are repeated until no edges remain. On the star this algorithm picks both endpoints of the first edge, that is, the center and one leaf. All edges are covered; the result is 2 vertices, twice the best.
6.5.4The edge-picking 2-approximation: code and trace
The Java code in the slides takes the edges in an array and processes them in order:
Set<Character> vertexCover(char[][] edges) {
Set<Character> cover = new HashSet<>();
for (char[] e : edges) {
char u = e[0], v = e[1];
if (!cover.contains(u) && !cover.contains(v)) {
cover.add(u); cover.add(v); } // both endpoints
}
return cover;
}Each edge is a two-character array: e[0] and e[1] are the endpoints. The cover is kept in a HashSet; the operations contains and add take O(1) on average. For each edge the loop checks that neither endpoint is in the cover. If so, the edge is not yet covered and both endpoints are added. If one of the endpoints is already in the cover, the edge is covered and is skipped. The code does not write a separate "mark as covered" operation; an edge becomes covered automatically the moment one of its endpoints enters the set, and it is skipped when its turn comes.
The cost is clear. Each edge is examined once, and each examination takes constant time on average. The total time is O(V + E). The memory is O(V) for the cover.
| Edge | Case | Cover (after) |
|---|---|---|
| (A, B) | both endpoints outside → A and B added | {A, B} |
| (A, C) | A in cover → skipped | {A, B} |
| (A, D), (A, E), (A, F) | A in cover → skipped | {A, B} |
| (B, C) | B in cover → skipped | {A, B} |
| (G, H) | both endpoints outside → G and H added | {A, B, G, H} |
| (G, I) | G in cover → skipped | {A, B, G, H} |
| (H, I), (H, K) | H in cover → skipped | {A, B, G, H} |
| (I, J) | both endpoints outside → I and J added | {A, B, G, H, I, J} |
| (J, K), (J, L) | J in cover → skipped | {A, B, G, H, I, J} |
Table 6.13 runs the code on the graph of Figure 6.20. The edges are given in the order above. Both endpoints of the first edge (A, B) are outside; A and B are added. The next five edges touching A or B are skipped. (G, H) is the second independent edge; G and H are added. (G, I), (H, I), and (H, K) are skipped. Both endpoints of (I, J) are outside; I and J are added. J covers the remaining two edges.
The result is the set {A, B, G, H, I, J} with 6 vertices. Since the best value is 5, the ratio is 6/5 = 1.2, far below the guaranteed 2. The three edges the algorithm picked, (A, B), (G, H), and (I, J), have no common endpoints. A set of edges with no common endpoints is called a matching. The key to the ratio proof is this matching.
6.5.5Why is the ratio at most 2?
The set C found by the edge-picking algorithm is a valid vertex cover and |C| ≤ 2 · OPT.
Validity is easy: when an edge is processed, either one of its endpoints is already in the set or both endpoints are added. In either case the edge is covered.
For the ratio, let M be the set of edges for which the algorithm adds both endpoints. An edge enters M only when neither endpoint is yet in the set. So two edges of M cannot share an endpoint; M is a matching. Now consider any cover, for example the best cover C*. C* must cover every edge of M. Because the edges of M share no endpoints, a vertex can cover at most one of them. Hence C* contains a separate vertex for each edge of M: OPT = |C*| ≥ |M|. The algorithm picks exactly |C| = 2 |M| vertices. Combining, |C| = 2 |M| ≤ 2 · OPT. □
There are other approaches too. The greedy algorithm that picks the vertex of highest degree looks natural. At each step it takes the vertex touching the most uncovered edges. On the graph of Figure 6.20, if ties in degree are broken alphabetically, this algorithm picks A, H, J, B, G in turn and finds the optimum with 5 vertices. But the ratio of this algorithm can only be bounded by O(log n), and graphs can be constructed on which the ratio really grows logarithmically. It is a good heuristic, but not a constant-ratio approximation algorithm.
Rounding a linear program gives a second 2-approximation. Each vertex gets a variable xv ∈ {0, 1}, and for each edge the constraint xu + xv ≥ 1 is written; Σ xv is minimized. If the integrality condition is dropped and 0 ≤ xv ≤ 1 is written, the problem becomes a linear program, the LP relaxation, which is solved in polynomial time. The value of the relaxation is less than or equal to OPT. Then the vertices with xv ≥ 1/2 are chosen. Since in every edge constraint at least one of the two variables reaches 1/2, the result is a valid cover. Since every chosen vertex has value at least 1/2, the number of elements is at most twice the value of the relaxation.
No constant ratio noticeably better than 2 is known. If the Unique Games Conjecture is true, it has been shown that for no ε > 0 is there a polynomial-time algorithm with ratio 2 − ε (Khot and Regev, 2008). The seemingly simple edge-picking algorithm reaches the best possible constant ratio under this conjecture.
Adding only one endpoint of the edge. This makes the algorithm look less wasteful, but on the star graph the ratio grows to n. Adding both endpoints is the condition for being able to compare with the best solution: the matching proof works only when the selected edges share no endpoints. Conversely, if the edges whose two endpoints are added did not form a matching, no lower bound could be built.
6.5.6NP-completeness: the reduction from 3-SAT
That the decision version of vertex cover is NP-complete is shown by a reduction. A reduction transforms every instance of a known NP-complete problem into an instance of vertex cover in polynomial time, so that the two instances have the same answer. 3-SAT is used as the source problem. In 3-SAT a logic formula is a conjunction ("and") of clauses, each consisting of three literals; each clause is a disjunction ("or") of literals. A literal is a variable or its negation. The question is whether there is an assignment of values that makes the formula true.
From a formula with l variables and m clauses, the reduction builds the following graph:
- For each variable xi, two vertices, xi and ¬xi, with an edge between them. To cover this edge, one of the two vertices must be chosen; the choice determines the value of the variable.
- For each clause, a triangle with three vertices; the vertices are labeled with the literals of the clause. To cover a triangle, at least two of its three vertices must be chosen.
- Each triangle vertex is joined by an edge to the variable vertex with the same label.
The cover size sought is k = l + 2m: one vertex from each variable edge and two from each triangle. The graph has 2l + 3m vertices and l + 6m edges; the construction takes polynomial time.
The example formula in the slides is φ = (x1 ∨ x1 ∨ x2) ∧ (¬x1 ∨ ¬x2 ∨ ¬x2) ∧ (¬x1 ∨ x2 ∨ x2). It has two variables and three clauses; the graph has 4 + 9 = 13 vertices and 2 + 9 + 9 = 20 edges. The size sought is k = 2 + 2 · 3 = 8.
The assignment that satisfies the formula is x1 = false, x2 = true. The cover is built from this assignment as follows. Because x1 is false, ¬x1 is chosen from its variable edge; because x2 is true, x2 is chosen. Every clause has a true literal. The triangle vertex of that literal is left out and the other two vertices are chosen. The connecting edge of the vertex left out is covered by the vertex chosen on the variable side. In C1 the true literal is x2; the two x1 vertices are chosen. In C2 the true literal is ¬x1; the two ¬x2 vertices are chosen. In C3 the true literal is ¬x1; the two x2 vertices are chosen.
In the end 8 vertices are chosen and all 20 edges are covered (Figure 6.24). A verification script confirmed, by trying all possibilities, that the minimum cover of this graph really is 8 and that the only assignment satisfying the formula is x1 = false, x2 = true.
The reverse direction also holds. A cover of size k = l + 2m contains exactly one vertex from each variable edge and exactly two from each triangle. These structures need at least one and at least two vertices, and the total is exactly k. The vertices chosen on the variable side define an assignment. In each triangle, the connecting edge of the vertex left out must be covered; this is possible only if its partner on the variable side has been chosen. So that literal is true under the assignment and the clause is satisfied. Conclusion: φ is satisfiable if and only if the graph has a vertex cover of size l + 2m.
6.6Knapsack
In the 0/1 knapsack problem there are n items. Item i has value vi and weight wi. The capacity of the knapsack is W. We seek the set of items whose total weight does not exceed W and whose total value is largest. Each item is either taken whole or not at all. The problem is NP-hard. It is solved by dynamic programming in O(nW) time, but this time depends on the numerical value of W. Since W is written in the input with log W bits, the time is exponential in the size of the input.
6.6.1The ratio-ordered greedy rule
The most natural greedy rule is to sort the items by value per unit of weight. The items are put in decreasing order of the ratio vi / wi and examined in turn. An item that fits in the knapsack is taken, and one that does not fit is skipped. Sorting is the dominant cost; the time is O(n log n).
| Item | Value | Weight | Ratio | Decision |
|---|---|---|---|---|
| 6 | 20 | 7 | 2.86 | taken (weight 7) |
| 3 | 8 | 4 | 2.00 | does not fit (7 + 4 = 11) |
| 7 | 15 | 8 | 1.88 | does not fit |
| 2 | 5 | 3 | 1.67 | taken (weight 10) |
| 5 | 10 | 6 | 1.67 | does not fit |
| 1 | 3 | 2 | 1.50 | does not fit |
| 4 | 6 | 5 | 1.20 | does not fit |
Table 6.14 gives the seven-item example from the slides. The item with the highest ratio is 6 (20/7 ≈ 2.86) and it is taken; the knapsack now holds 7 kilograms. The next item, 3, weighs 4 kilograms and does not fit. Item 7 does not fit either. Item 2 weighs 3 kilograms and fills the knapsack to exactly 10 kilograms. After this no item fits. The greedy total value is 20 + 5 = 25. A verification script tried all 27 = 128 subsets; the best value is also 25, again consisting of items 2 and 6. In this example the greedy rule finds the optimum. Items 2 and 5 have equal ratios (5/3 = 10/6); in the table item 2 comes first.
If items could be divided, that is, if the problem were the fractional knapsack, this rule would always give the best result: a part of the first item that does not fit is taken, and the knapsack is exactly full. For the 0/1 version, however, the rule has no guarantee at all.
Let the capacity be W = 10 and let there be two items: (value 2, weight 1) and (value 10, weight 10). The ratios are 2 and 1. The greedy rule takes the first item first. Room for 9 kilograms remains in the knapsack, and the second item does not fit. The greedy value is 2. The best solution takes only the second item and reaches value 10. The ratio is 10 / 2 = 5. If the value and weight of the second item are made W, the ratio becomes W / 2; it gets arbitrarily bad as W grows.
6.6.2The improved rule: a 2-approximation
The source of the bad example is a single valuable item. The ratio ordering leaves it behind, and once small items take up room in the knapsack that item no longer fits. The fix is simple. The greedy value is compared with the value of the most valuable single item that fits in the knapsack by itself, and the larger is taken:
result = max( greedy value, most valuable single item that fits )
On the bad example this rule finds max(2, 10) = 10 and reaches the optimum. The general guarantee is 2.
Suppose the items whose weight exceeds W have been discarded at the start. If the greedy value is G and the value of the most valuable single item that fits is vmax, then max(G, vmax) ≥ OPT / 2.
Number the items 1, 2, …, n in ratio order. Let k be the first item that does not fit when the items are taken in order. The optimal value of the fractional knapsack is obtained as v1 + … + vk−1 plus a part of item k. A 0/1 solution is also a fractional solution; therefore
OPT ≤ v1 + … + vk−1 + vk
can be written. The greedy rule has taken all of the first k − 1 items and may then take other items that fit: G ≥ v1 + … + vk−1. Since item k fits by itself, vk ≤ vmax. Combining, OPT ≤ G + vmax ≤ 2 · max(G, vmax). If there is no item that does not fit, that is, if k does not exist, the greedy rule takes all the items and G = OPT. □
Let W = 15 and let the items, as (value, weight), be E1 (30, 10), E2 (20, 8), E3 (18, 7), E4 (6, 4). The ratios are 3.00, 2.50, 2.57, and 1.50. The ratio order is E1, E3, E2, E4. E1 is taken (10 kg). E3 does not fit (17 kg), E2 does not fit (18 kg), E4 fits (14 kg). The greedy value is 36. The most valuable single item that fits is E1 (30); the improved rule finds 36. The best solution takes E2 and E3: exactly 15 kg and value 38. The ratio is 38/36 ≈ 1.06. The upper bound in the proof can also be checked: here k is E3 and OPT = 38 ≤ 30 + 18 = 48. The fractional value is 30 + (5/7) · 18 ≈ 42.86, which is also greater than 38.
6.6.3A fully polynomial-time approximation scheme
The knapsack problem is among the problems that admit a ratio much better than 2. For every ε > 0 there is an algorithm that finds at least a (1 − ε) fraction of the best value and runs in O(n3/ε) time. This is a fully polynomial-time approximation scheme (FPTAS).
The idea is to scale the values. The knapsack problem has a dynamic program built over values: for each value x, the table holds "the weight of the lightest set of items whose total value is exactly x". The table has as many entries as the sum of the values, and the time is O(n · Σ vi). When the values are large, this time is large. The FPTAS divides the values by a number K = ε · vmax / n and rounds down: v'i = ⌊vi / K⌋. Each scaled value is at most n/ε and their sum is at most n2/ε. With these small values the dynamic program runs in O(n · n2/ε) = O(n3/ε) time and finds the optimal solution of the scaled problem.
The loss caused by rounding is bounded. Each item loses at most K of its value; since the best set contains at most n items, the total loss is at most nK = ε · vmax ≤ ε · OPT. Therefore the true value of the set found is at least (1 − ε) · OPT. The summary table in the slides writes this ratio as 1 + ε, by analogy with the minimization form; for small ε the two ways of writing express the same guarantee.
6.7Power iteration
The algorithms so far produced approximate solutions to combinatorial problems. In numerical computation, "approximation" takes another form: instead of finding the exact value in a finite number of steps, one produces a sequence that gets a little closer to it at each step. This behavior is called convergence. A typical example of convergence is power iteration, which finds the largest eigenvalue of a matrix.
6.7.1Dominant eigenvalue and eigenvector
For a square matrix A, a nonzero vector v satisfying A · v = λ · v is called an eigenvector, and the number λ its eigenvalue. An eigenvector is a vector that, when multiplied by the matrix, does not change direction but only stretches or shrinks by the factor λ. An n × n matrix has at most n eigenvalues. The one with the largest absolute value is called the dominant eigenvalue and is denoted λ1; its eigenvector is v1.
Power iteration is an iterative method that repeatedly multiplies a nonzero vector x0 by the matrix A, normalizing at each step, and converges to the dominant eigenvector v1 and the dominant eigenvalue λ1.
Methods that compute all the eigenvalues exactly take O(n3) time. This is acceptable if the matrix has thousands of rows; it is not if it has billions. Power iteration gives only the dominant eigenvalue and eigenvector, and only approximately, but each step is a single matrix–vector product. This product takes O(n2) on a dense matrix and as many operations as there are nonzero entries on a sparse one. For huge sparse matrices it is often the only method that can be used.
The simplest example is a diagonal matrix. The matrix A = [[2, 0], [0, 1]] has eigenvalues 2 and 1 and eigenvectors (1, 0) and (0, 1). Take x0 = (1, 1). With each multiplication the first component doubles and the second stays the same: Ak x0 = (2k, 1). The direction of the normalized vector gradually turns toward (1, 0) (Figure 6.25). The ratio of the second component to the first is 2−k. The error halves at each step. For this ratio to fall below 10−3 we need 2k > 1000; since 29 = 512 and 210 = 1024, k = 10 steps suffice.
6.7.2The steps and why it converges
The steps of the algorithm are as follows:
- Fix a matrix A and choose a nonzero starting vector x0. Choosing it at random is common.
- Multiply the vector by the matrix: y = A · xk.
- Normalize the new vector, that is, bring its norm (length) to 1: xk+1 = y / ‖y‖.
- Repeat the second and third steps for the desired number of steps, or until the change in the vector becomes small enough.
In the end xk converges to v1. There are two ways to estimate the eigenvalue. The length before normalization, ‖A · xk‖, converges to |λ1|. For symmetric matrices a faster-converging estimate is the Rayleigh quotient: when ‖xk‖ = 1, λ ≈ xkT A xk.
Why the method works can be seen by writing the starting vector in terms of eigenvectors. Let the eigenvectors of A form a basis and let x0 = c1 v1 + c2 v2 + … + cn vn. Each multiplication by A multiplies each component by its own eigenvalue:
Ak x0 = λ1k [ c1 v1 + c2 (λ2/λ1)k v2 + … + cn (λn/λ1)k vn ]
If |λ1| > |λ2| ≥ … ≥ |λn|, then all the factors (λi/λ1)k inside the square brackets decay geometrically to zero. What remains is c1 v1. Normalization removes the leading factor λ1k, and the vector approaches the unit vector in the direction of v1. The component that dies out most slowly is that of v2. So the error shrinks by a factor of about |λ2/λ1| at each step. If the ratio is 0.1, one correct digit is gained per step; if the ratio is 0.99, about 230 steps are needed for one digit.
The formula shows both conditions clearly. First, c1 ≠ 0 must hold; if the starting vector is chosen orthogonal to v1, the v1 component is absent and in theory never appears. In practice rounding errors create a small v1 component, but convergence is delayed. The probability that a randomly chosen vector is exactly orthogonal is zero. Second, |λ1| > |λ2| must hold. If there are two eigenvalues equal in absolute value, for example λ1 = 3 and λ2 = −3, the second component does not die out and the vector may oscillate between two directions.
6.7.3Convergence step by step
The example in the slides is a symmetric matrix: A = [[2, 1], [1, 3]]. The characteristic equation is (2 − λ)(3 − λ) − 1 = λ2 − 5λ + 5 = 0, and its roots are λ1 = (5 + √5)/2 ≈ 3.618 and λ2 = (5 − √5)/2 ≈ 1.382. The dominant eigenvector, normalized to length 1, is v1 ≈ (0.5257, 0.8507). The ratio is λ2/λ1 ≈ 0.382. The starting vector is x0 = (1, 0) and its error is ‖x0 − v1‖ ≈ 0.974.
| k | A · xk−1 | xk | λ estimate | Error |
|---|---|---|---|---|
| 0 | — | (1, 0) | — | 0.974 |
| 1 | (2.000, 1.000) | (0.894, 0.447) | 3.000 | 0.5465 |
| 2 | (2.236, 2.236) | (0.707, 0.707) | 3.500 | 0.2313 |
| 3 | (2.121, 2.828) | (0.600, 0.800) | 3.600 | 0.0899 |
| 4 | (2.000, 3.000) | (0.5547, 0.8321) | 3.61538 | 3.4 · 10−2 |
| 5 | (1.942, 3.051) | (0.5369, 0.8437) | 3.61765 | 1.3 · 10−2 |
| 6 | (1.917, 3.068) | (0.5300, 0.8480) | 3.61798 | 5.0 · 10−3 |
| 7 | (1.908, 3.074) | (0.5274, 0.8496) | 3.61803 | 1.9 · 10−3 |
| 8 | (1.904, 3.076) | (0.5264, 0.8503) | 3.61803 | 7.3 · 10−4 |
| 9 | (1.903, 3.077) | (0.5260, 0.8505) | 3.618034 | 2.8 · 10−4 |
Table 6.15 gives the first nine steps. In the first step A · (1, 0) = (2, 1). Its length is √5 ≈ 2.236, and dividing gives x1 = (0.894, 0.447). The Rayleigh quotient is x1T A x1 = 3.0. In the second step A · x1 = (2.236, 2.236); the vector turns exactly to the diagonal direction and λ ≈ 3.5. In the third step x3 = (0.6, 0.8) and λ ≈ 3.6 are found. In the following steps the estimate of λ quickly settles at 3.618.
The error column shows the rate of convergence clearly. The ratio of two successive errors is 0.42 and 0.39 in the first steps; after the fourth step it settles at 0.382 ≈ λ2/λ1. The error shrinks by a factor of about 0.38 at each step. On a log-scale plot this behavior is a straight line with slope log10 0.382 ≈ −0.42 (Figure 6.26). In numerical analysis such convergence is called linear or geometric convergence. Each step gains about 0.42 decimal digits; two and a half steps are needed for one digit. The eigenvalue estimate converges faster than the eigenvector: for a symmetric matrix the error of the Rayleigh quotient is proportional to the square of the vector error. At the ninth step, when the vector error is 2.8 · 10−4, λ is correct to six digits.
6.7.4Java code and a 3 × 3 example
The Java code in the slides runs the algorithm for a fixed number of steps:
double[] powerIteration(double[][] a, int steps) {
int n = a.length;
double[] x = new double[n];
Arrays.fill(x, 1.0); // x₀ ≠ 0, not orthogonal to v₁
for (int k = 0; k < steps; k++) {
double[] y = new double[n];
for (int i = 0; i < n; i++) // y = A·x
for (int j = 0; j < n; j++)
y[i] += a[i][j] * x[j];
double norm = 0;
for (double yi : y) norm += yi * yi;
norm = Math.sqrt(norm);
if (norm == 0) break; // A·x = 0
for (int i = 0; i < n; i++) // ‖x‖ = 1
x[i] = y[i] / norm;
}
return x;
}The method takes the matrix a and the number of steps steps. The starting vector is the vector with all components equal to 1. This choice is simple and satisfies the condition c1 ≠ 0 for most matrices. In each round of the outer loop, the product y = A · x is first computed with two nested loops; y[i] is the dot product of row i of A with x. Then the Euclidean norm of y is found as the square root of the sum of the squares of its components. If the norm is zero (A · x = 0), the division is undefined; break stops the loop at that point. Finally x is set to y / norm. The method returns the final x; the value norm is not returned, but it can be used as an estimate of λ1.
In each step the product performs n2 multiplications and additions; normalization takes O(n). The total time for steps steps is O(steps · n2). The memory is O(n) for x and y; the matrix itself is not modified. The code uses no stopping criterion. In practical applications the loop is stopped when the difference between two successive x falls below a threshold.
The example matrix in the slides is the following:
A = [[0.511, 0.32, 0.12], [0.211, 0.62, 0.12], [0.311, 0.12, 0.16]], x0 = (1, 1, 1)
The eigenvalues of this matrix are about 0.9008, 0.3, and 0.0902. The ratio is λ2/λ1 = 0.3 / 0.9008 ≈ 0.33; convergence is fast. One property of the matrix also stands out. The sums of the first two entries of the first and second rows are the same (0.511 + 0.32 = 0.211 + 0.62 = 0.831) and their third entries are equal. So if the first two components of x are equal, those of A · x stay equal. Since x0 = (1, 1, 1) has this property, x1 = x2 holds at every step of the iteration.
k | y = A · x | norm = ‖y‖ | New x |
|---|---|---|---|
| 0 | (0.9510, 0.9510, 0.5910) | 1.4690 | (0.6474, 0.6474, 0.4023) |
| 1 | (0.5862, 0.5862, 0.3434) | 0.8974 | (0.6533, 0.6533, 0.3827) |
| 2 | (0.5888, 0.5888, 0.3428) | 0.9005 | (0.6539, 0.6539, 0.3807) |
| 3 | (0.5890, 0.5890, 0.3427) | 0.9008 | (0.6539, 0.6539, 0.3805) |
| 4–7 | (0.5891, 0.5891, 0.3427) | 0.9008 | (0.6539, 0.6539, 0.3805) |
In the first step y[0] is the product of the first row with x: 0.511 · 1 + 0.32 · 1 + 0.12 · 1 = 0.951. y[1] is 0.951 for the same reason, and y[2] is 0.311 + 0.12 + 0.16 = 0.591. The norm is √(0.9512 + 0.9512 + 0.5912) ≈ 1.4690. Dividing gives x = (0.6474, 0.6474, 0.4023). This vector has length 1; the numbers now neither grow nor shrink.
In the second step y = (0.5862, 0.5862, 0.3434). The ratio of the components is very close to that of the first step; the direction has changed little. The norm is 0.8974. In the third step the norm rises to 0.9005 and in the fourth to 0.9008, where it stays. We see that the norm converges to λ1 = 0.9008. After the fourth step the vector no longer changes to four digits: v1 ∝ (0.6539, 0.6539, 0.3805).
The trace in the slides stops at steps = 3 and returns x ≈ (0.6539, 0.6539, 0.3807); the third component settles at 0.3805 one step later. The number of steps must be chosen according to the desired accuracy: for the error to fall by a factor of 10−d, about d / log10(λ1/|λ2|) steps are needed. Here the ratio is about 3, and each step gains slightly less than half a digit (log10 3 ≈ 0.48).
Skipping normalization. If x is not normalized at each step, Ak x0 is computed directly. If |λ1| > 1, the components grow at rate λ1k and exceed the range of the double type within a few hundred steps. If |λ1| < 1, as in the 3 × 3 example, the components shrink to zero and the significant digits are lost. Normalization corrects only the scale; it does not change the direction, that is, the information being sought.
6.7.5Limitations and applications
The strengths of power iteration come from its simplicity. It uses only matrix–vector products. It does not modify the matrix itself, and as extra memory it needs only a few vectors, that is, O(n) space. It can therefore be applied to sparse matrices with billions of rows.
Its limitations are also clear. It finds only the dominant eigenvalue. If |λ2| is close to |λ1| it converges very slowly; if they are equal it may not converge. If the starting vector is chosen orthogonal to v1 (c1 = 0), it fails in theory.
The best-known application of the method is Google's PageRank computation. The importance of a page is determined by the importance of the pages that link to it; this definition is an eigenvector equation. The importance values of the pages are the dominant eigenvector of the web link matrix. The matrix has billions of rows but is very sparse, and power iteration reaches sufficient accuracy in a few dozen steps. Its derivatives are also widespread: inverse iteration finds the smallest eigenvalue, shifted iteration the eigenvalue closest to a given value; the Lanczos and Arnoldi methods compute several eigenvalues together. In principal component analysis (PCA) the first principal component can also be found this way.
6.8Comparison and common mistakes
Table 6.17 puts the algorithms studied in these notes side by side by problem, ratio, and running time.
| Problem | Algorithm | Ratio | Time |
|---|---|---|---|
| TSP (general) | Nearest neighbor (heuristic) | no guarantee | O(n2) |
| Metric TSP | MST + preorder + shortcuts / Christofides | 2 / 1.5 | O(n2) / O(n3) |
| TSP | 2-opt local search | no guarantee | O(n2) per pass |
| Machine scheduling | List scheduling / LPT | 2 − 1/m / 4/3 − 1/(3m) | O(n log m) / O(n log n) |
| Vertex cover | Pick an edge, add both endpoints | 2 | O(V + E) |
| 0/1 knapsack | max(ratio-ordered greedy, best single item) / FPTAS | 2 / 1 + ε | O(n log n) / O(n3/ε) |
| Dominant eigenvalue | Power iteration | error ∝ |λ2/λ1|k | O(n2) per step |
The common mistakes treated in various places in these notes are the following:
- Mistaking a heuristic for an approximation algorithm. Nearest neighbor and 2-opt give good results, but they have no ratio guarantee. An approximation algorithm requires a proven ρ.
- Writing the ratio upside down. For minimization C ≤ ρ · C*, for maximization C ≥ C* / ρ. ρ is always at least 1.
- Adding one endpoint in a cover. Adding only one endpoint of an edge can give a result n times worse on a star graph; the 2-approximation adds both endpoints.
- Forgetting the triangle inequality. The shortcut step of the MST-based 2-approximation does not lengthen the route only for metric TSP.
- Assuming a metaheuristic is exact. Simulated annealing and genetic algorithms do not guarantee reaching the optimum; they are run several times with different seeds and parameters and the best result is kept.
- Skipping normalization. In power iteration, if
xis not normalized at each step, the numbers overflow (|λ1| > 1) or shrink to zero.
6.9Summary
- Approximation algorithm: for an NP-hard optimization problem it runs in polynomial time and, on every input, satisfies max(C/C*, C*/C) ≤ ρ; for minimization C ≤ ρ · C*, for maximization C ≥ C*/ρ.
- Types of methods: exact algorithm, approximation algorithm, PTAS, FPTAS (time polynomial in 1/ε as well), heuristic and metaheuristic (no guarantee).
- TSP: brute force (n − 1)!/2 tours, Held–Karp O(n2 2n). For general TSP, if P ≠ NP there is no constant-ratio approximation. Nearest neighbor runs in O(n2) but its ratio can be Θ(log n).
- Metric TSP: w(T) ≤ OPT and the tour with shortcuts is ≤ 2 · w(T); 287.7 / 282.5 on seven cities. Christofides gives the ratio 1.5.
- 2-opt: gain Δ = d(a,c) + d(b,d) − d(a,b) − d(c,d); no crossing edges remain at a local optimum; from 1269.8 to 430.8 in 48 moves on 28 cities. Metaheuristics can escape local optima but give no guarantee.
- Machine scheduling: list scheduling 2 − 1/m, LPT 4/3 − 1/(3m); lower bounds Σp/m and max p; both bounds are tight.
- Vertex cover: both endpoints of an uncovered edge are added; the selected edges form a matching, |C| = 2|M| ≤ 2 · OPT, time O(V + E). In the 3-SAT reduction k = l + 2m.
- Knapsack: max(ratio-ordered greedy, most valuable single item) is a 2-approximation; value scaling gives an FPTAS.
- Power iteration: xk+1 = A xk / ‖A xk‖ → v1; the error shrinks by a factor of about |λ2/λ1| at each step; the conditions are c1 ≠ 0 and |λ1| > |λ2|.
6.10Key terms
- approximation algorithm
- approximation ratio
- approximation scheme (PTAS / FPTAS)
- heuristic
- metaheuristic
- traveling salesman problem (TSP)
- Hamiltonian cycle
- triangle inequality
- minimum spanning tree (MST)
- nearest neighbor
- local search
- local optimum
- simulated annealing
- list scheduling
- makespan
- longest processing time first (LPT)
- vertex cover
- matching
- reduction
- LP relaxation
- 0/1 knapsack
- power iteration
- convergence
6.11Test Yourself
An approximation algorithm with ratio 2 finds a solution of cost 50 on a minimization problem. In what range does the best cost lie? What would the range be if the same result were found on a maximization problem?
Answer
For minimization, since 50 ≤ 2 · OPT, OPT ≥ 25; since the best solution cannot be worse than the one found, OPT ≤ 50. The range is [25, 50]. For maximization, since 50 ≥ OPT / 2, OPT ≤ 100, and OPT ≥ 50. The range is [50, 100].
Let the distance matrix of four cities be, row by row, 0: (0 1 15 6), 1: (1 0 7 3), 2: (15 7 0 2), 3: (6 3 2 0). What tour does nearest neighbor find when started from 0? What is the best tour? Is the matrix metric?
Answer
The nearest city to 0 is 1 (1). From 1 the unvisited cities are 2 (7) and 3 (3); 3 is chosen. From 3 the only candidate is 2 (2). From 2 we return to 0 (15). The tour is 0 → 1 → 3 → 2 → 0, length 1 + 3 + 2 + 15 = 21. With four cities there are three distinct tours: 0 → 1 → 2 → 3 → 0 (16), 0 → 1 → 3 → 2 → 0 (21), and 0 → 2 → 1 → 3 → 0 (31). The best is 16. The matrix is not metric: d[0][2] = 15 > d[0][1] + d[1][2] = 8. The cheap choices left the expensive return edge for the end.
Let the points be a (0, 0), b (3, 4), c (6, 0), d (3, −4), and let the tour contain the edges (a, b) and (c, d). What is the 2-opt gain; is the move made? Do the edges cross?
Answer
d(a, b) = d(c, d) = 5, d(a, c) = 6, d(b, d) = 8. Δ = 6 + 8 − 5 − 5 = 4 > 0; the move would lengthen the tour and is not made. The two edges do not cross: (a, b) lies above the axis and (c, d) below it. For pairs of edges that do not cross, the 2-opt gain can be positive; the geometric result guarantees an improvement only for crossing edges.
Jobs with processing times 1, 2, 3, 4, 5, 6 are given in this order to m = 3 machines by list scheduling. What are the machine loads and Cmax? What does LPT find? What is the best value?
Answer
List: 1, 2, 3 go to the three machines (loads 1, 2, 3). 4 goes to the least loaded, the first machine (5), 5 to the second (7), 6 to the third (9). The loads are 5, 7, 9; Cmax = 9. The LPT order is 6, 5, 4, 3, 2, 1: 6, 5, 4 go to the three machines; 3 goes to the least loaded, the third (7), 2 to the second (7), 1 to the first (7). The loads are 7, 7, 7. Since the total work is 21, the lower bound is 7; LPT finds the optimum. The ratio of list scheduling is 9/7 ≈ 1.29, below the bound 2 − 1/3 ≈ 1.67.
The edges of the six-vertex cycle 1–2–3–4–5–6–1, namely (1,2), (2,3), (3,4), (4,5), (5,6), (6,1), are given in this order to the edge-picking 2-approximation. How many vertices are chosen? What would the result be if the edges were given in the order (2,3), (5,6), (1,2), (3,4), (4,5), (6,1)? What is the best value?
Answer
In the first order (1,2), (3,4), and (5,6) are chosen; the result is 6 vertices. In the second order (2,3) and (5,6) are chosen; one endpoint of each of the remaining four edges is in the cover, and the result is {2, 3, 5, 6}, 4 vertices. The best cover has 3 vertices, for example {1, 3, 5}. The ratios are 2 and 4/3. The order of the edges changes the result, but the guarantee holds for every order.
Let W = 50 and let the items, as (value, weight), be (60, 10), (100, 20), (120, 30). What do the ratio-ordered greedy rule, the improved rule, and the best 0/1 solution find? What is the value of the fractional version?
Answer
The ratios are 6, 5, and 4. The greedy rule takes (60, 10) and (100, 20) (30 kg); (120, 30) does not fit (60 kg). The greedy value is 160. The most valuable single item that fits is 120; the improved rule finds max(160, 120) = 160. The best 0/1 solution takes (100, 20) and (120, 30): exactly 50 kg, value 220. The ratio is 220/160 = 1.375 ≤ 2. In the fractional version the first two items and 2/3 of the third are taken: 60 + 100 + 80 = 240.
Carry out the first step of power iteration for A = [[2, 1], [1, 2]] and x0 = (1, 0). Given that the eigenvalues are 3 and 1, about how many steps are needed for the error to fall by a factor of 10−6?
Answer
y = A · x0 = (2, 1), ‖y‖ = √5 ≈ 2.2361, x1 = (0.8944, 0.4472). The Rayleigh quotient is x1T A x1 = 2.8; the true value is 3. The error shrinks by a factor of about 1/3 per step. For (1/3)k < 10−6, k > 6 / log10 3 ≈ 12.6, so 13 steps are needed.
Is a TSP instance in which all distances are 1 or 2 metric? Can the MST-based 2-approximation be applied to it?
Answer
Yes, it is metric. For all i, j, k, dij ≤ 2; also dik + dkj ≥ 1 + 1 = 2. The triangle inequality always holds. So the MST-based algorithm can be applied and the guarantee of 2 · OPT is valid. The construction in the Hamiltonian cycle proof, on the other hand, is not metric because it makes the heavy edge ρn + 1; once the weights are restricted to 1 and 2, that proof does not work.
6.12Further reading
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapter 35: approximation algorithms for vertex cover, metric TSP, and set cover, with the full proof of the Hamiltonian cycle reduction.
- D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms (2011): presents the techniques of greedy algorithms, local search, linear programming, and approximation schemes in an orderly sequence; the electronic version of the book is free on the authors' website.
- V. V. Vazirani, Approximation Algorithms (2001): gives covering problems, the knapsack FPTAS, and primal–dual methods with short and precise proofs.
- G. H. Golub and C. F. Van Loan, Matrix Computations (4th ed., 2013): convergence analysis of power iteration, inverse and shifted iteration, the Lanczos method.
6.13References
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 (Chapter 35: Approximation Algorithms).
- N. Christofides, “Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem”, Report 388, Carnegie Mellon University, 1976.
- G. H. Golub, C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013.
- R. L. Graham, “Bounds on Multiprocessing Timing Anomalies”, SIAM Journal on Applied Mathematics 17(2), 1969.
- A. R. Karlin, N. Klein, S. Oveis Gharan, “A (Slightly) Improved Approximation Algorithm for Metric TSP”, Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC), 2021.
- M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2012 (3-SAT → vertex cover reduction).
- V. V. Vazirani, Approximation Algorithms, Springer, 2001.
- D. P. Williamson, D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.
Related pages: Chapter 6 slides · © Sercan Külcü. All rights reserved.