Why approximate
The preceding units show that many optimization problems are NP-hard, so no polynomial-time algorithm is known that always finds an optimal solution. Unless every such problem can be solved exactly in polynomial time, we must give up something. An approximation algorithm gives up optimality but not provability: it runs in polynomial time on every instance and comes with a proven bound on how far its answer can be from the optimum. This unit develops the two basic techniques for such proofs. The first compares the algorithm's output with an easily computed lower bound on the optimum (a maximal matching). The second compares the algorithm's total cost with the optimum by charging the cost to the items being covered (greedy set cover). The unit assumes the definitions of graphs and of NP-hardness from the earlier units of this chapter.
Definitions
Definition 4.6.1
(Approximation ratio)
An optimization problem of minimization type assigns to each instance a set of feasible solutions, each with a nonnegative cost; denotes the least cost of a feasible solution. An algorithm is a -approximation algorithm (for a constant ) if, on every instance , it runs in time polynomial in the size of , outputs a feasible solution, and the cost of its output satisfies
The ratio may also depend on the instance size, as in the second half of this unit. A ratio guarantee is a statement about all instances, so showing that an algorithm happens to be optimal on some instances proves nothing, and showing that it is wasteful on one instance only gives a lower bound on its true ratio.
Definition 4.6.2
(Vertex cover, matching and maximal matching)
Let be a finite undirected graph. A vertex cover is a set such that every edge has at least one endpoint in . The minimum vertex cover problem asks for a vertex cover of least size. A matching is a set of edges no two of which share an endpoint; it is maximal if no edge of can be added to without destroying the matching property. Maximal is weaker than maximum: a maximal matching cannot be extended, but a larger matching may exist elsewhere.
Definition 4.6.3
(Set cover and harmonic numbers)
In the minimum set cover problem we are given a finite universe with and sets whose union is . A cover is a set of indices with , and its cost is . The th harmonic number is ; it satisfies because for .
Vertex cover by maximal matching
The algorithm repeatedly takes an uncovered edge and puts both of its endpoints into the cover.
APPROX-VERTEX-COVER(G):
C = empty set; M = empty set
while G still has an edge uv:
add u and v to C; add uv to M
delete u, v and every edge incident to u or v from G
return C
Theorem 4.6.4
(Two-approximation for vertex cover)
On every graph , the algorithm terminates in time , the set is a maximal matching, the output is a vertex cover with , and
Proof
(Two-approximation by a maximal matching)
Each iteration deletes at least the edge , so the loop terminates after at most iterations. With adjacency lists and one mark per vertex, an iteration costs time proportional to the number of deleted edges plus a constant, which gives the stated total.
When is added to , every edge incident to or is deleted, so no later edge of uses or . Hence the edges of are pairwise disjoint and . The loop ends only when no edge remains; every edge of was either added to or deleted because it touched an endpoint already in . Thus every edge has an endpoint in , and is a vertex cover. If some edge could be added to at the end, it would be an edge of none of whose endpoints is in , contradicting the last remark; so is maximal.
For optimality, let be a minimum vertex cover. Every edge of has an endpoint in , and distinct edges of have distinct endpoints, so contains at least different vertices: . Therefore .
The proof contains a general pattern: a polynomial-time computable lower bound () on the optimum is compared with the cost of the output. The algorithm never needs to know .
Concept lensCombinatorial
Vertex cover as a special set cover
Build a set-cover instance from : the universe is , and each vertex gives the set of edges incident to . A set is a vertex cover exactly when , so vertex covers are the covers of this instance, with the same cost. Every element (edge) lies in exactly two sets. A matching is a family of elements no two of which share a set, so each needs its own set in any cover; this is the bound restated. Taking both endpoints of a matching edge takes all sets containing that element.
Greedy set cover
The greedy rule repeatedly picks the set containing the most elements that are still uncovered.
GREEDY-SET-COVER(U, S_1..S_m):
R = U; J = empty list
while R is not empty:
choose j maximizing |S_j intersect R| (break ties by smallest index)
append j to J; R = R minus S_j
return J
Theorem 4.6.5
(Harmonic guarantee of greedy set cover)
Let be the minimum size of a cover. The greedy algorithm returns a cover of size at most .
Proof
(Harmonic bound for greedy set cover)
Termination: because the union of all sets is , as long as some set meets , so each iteration removes at least one element, and the loop ends after at most iterations with ; hence is a cover.
Key lemma. If elements remain uncovered, then some set contains at least of them. Indeed, an optimal cover of sets covers all remaining elements, so the sets together contain at least remaining elements counted with multiplicity, and by the pigeonhole principle one of them contains at least . Greedy picks a set with at least as many new elements as that one.
Charging. Whenever greedy picks a set that covers new elements, give each of these elements the price . The total of all prices equals the number of sets chosen. List the elements in the order in which they are covered (elements covered in the same iteration in any order): . When is covered, the elements are all still uncovered at the start of that iteration, so elements remained. By the key lemma greedy covered new elements, and therefore
Summing over gives .
Proof X-ray
Why prices turn a count into a sum
The proof converts the number of chosen sets into a sum over elements: giving each newly covered element the price makes the total price equal , so the bound can be proved one element at a time. The non-obvious step is the order in which elements are listed. Whatever order is used inside one iteration, the inequality still holds for , because it only uses that are all uncovered when that iteration begins.
The optimum enters in exactly one place, the pigeonhole step of the key lemma, and only as an upper bound on how many sets an optimal cover of the remaining elements needs; that is why the argument survives after greedy has already removed elements. The bounds add up to , which closes the proof. Without the key lemma the price of an element could be as large as for every element, giving only the useless bound .
Worked examples
Worked example 4.6.6
(vertex cover on a path of six vertices)
Let be the path with edges . Run the algorithm taking edges in the listed order. Take : put in and delete . Next remaining edge is : put in , delete . Next is : put in . Now and , so . The set covers (by ), (by ) and (by ), so , and ; hence and the ratio is exactly for this order.
The answer depends on the order. If the first edge taken is (delete ), then (delete ), we get and with . Both outputs satisfy the theorem.
Worked example 4.6.7
(greedy set cover is not always optimal)
Let with , , . Greedy first takes (four new elements, against three for each other set). Then ; covers and covers , each one new element; the tie goes to . Then and is taken. Greedy returns three sets. The sets alone cover , so and the output is times optimal. The theorem guarantees only , hence , consistent with .
Worked example 4.6.8
(the factor 2 cannot be improved for this algorithm)
Let be the complete bipartite graph with sides of size . Every maximal matching of is perfect: if a vertex of and a vertex of were both unmatched, the edge between them could be added. So the algorithm always outputs all vertices. The side alone is a vertex cover, since every edge has an endpoint in , so . By the theorem , so and the output is exactly twice the optimum, for every . The analysis of this algorithm is therefore tight.
Common mistakes and subtle points
Common mistake
(Reading the ratio as structural similarity)
A -approximation is a worst-case guarantee on cost, not a promise that the output resembles an optimal solution: the two outputs in the six-vertex path example use different vertices, and neither need resemble an optimal cover.
Counterexample mode
Taking one endpoint of each matching edge
A tempting shortcut is to keep only one endpoint of each matching edge, which would halve the cover. On the path , the set is a maximal matching: the only other edge, , shares an endpoint with both. Choosing and leaves uncovered, so the shortcut fails. Both endpoints are needed: maximality says only that every edge outside touches a matched vertex, and covering that edge requires the matched vertex to be in , whichever endpoint it is.
Common mistake
(Maximal versus maximum matching)
The matching must be maximal for the cover to be valid, but it does not need to be maximum. The bound holds for every matching , so the proof applies to whichever maximal matching the algorithm happens to build.
Common mistake
(The optimum of the remaining elements)
In the set cover analysis, is the optimum for the original instance. After some sets have been chosen, the optimum for the uncovered elements is at most but may be smaller; the key lemma only needs the upper bound , which is the direction that holds.
The harmonic bound depends on , so it is not a constant-factor guarantee, and nothing in this unit shows that it is the best possible.
Exercises
Quick check
(Run the vertex-cover algorithm on the 5-cycle with vertices and edges , taking edges in this order. List and , and find .)
One vertex covers at most two edges of a cycle.
Solution · Answer
Take : add to and delete . The remaining edges are . Take : add and delete . No edges remain. So and , of size . A vertex cover needs at least vertices because each vertex covers at most two of the five edges; covers (by ), (by ) and (by ). So and the ratio is .
Exercise 4.6.9
(Let be any matching in a graph . Prove that every vertex cover of has at least vertices. Explain why this inequality alone does not show that the output of the vertex-cover algorithm has at most vertices.)
Core
Solution(3)
- 1
Pick a covering endpoint for each matching edge
Let be a vertex cover. For each edge of , choose one endpoint lying in .
Because: A vertex cover has an endpoint on every edge, in particular on every edge of .
- 2
Show the chosen endpoints are distinct
Key step
Two different edges of have no common endpoint, so they yield different chosen vertices. Hence contains at least vertices.
Because: Edges of a matching share no endpoints.
- 3
Compare with the algorithm's output
The inequality only bounds from below by . The output has vertices, which exceeds and can exceed : in the six-vertex path example, while .
Exercise 4.6.10
(Let with , , , , . Run greedy set cover (ties by smallest index) and prove that its output is optimal.)
Core
Solution(3)
- 1
Run greedy
is the largest set, so take ; then . The new elements are for (3), for (2), for (2) and for (2). Take ; then and the first set containing is . The output is , three sets.
- 2
Show that no two sets cover
Key step
The sets have sizes . Two sets cover only if their sizes sum to at least . Without the largest sum is . With the partner must have size , so it is or ; but and , so these pairs cover at most elements.
Because: A lower bound of on the optimum matches the greedy output.
- 3
Conclude optimality
Hence , and greedy uses sets, so and greedy is optimal here.
Quick check
(In the set-cover example where greedy is not optimal (, , , ), write down the price of each element in the order it is covered, check that the prices add up to the number of sets chosen, and check for every .)
Greedy picks , then , then , and .
Solution · Answer
Greedy takes and covers , each at price . Then it covers with at price and with at price . The total is , the number of sets chosen. With and the bounds for are . The prices are at most respectively, so all six inequalities hold; for example for and for .
Quick check
(Let the edges of a graph with vertices form a perfect matching of edges (no other edges). Show that the vertex-cover algorithm outputs a cover with exactly vertices, and give .)
Use the lower bound .
Solution · Answer
Each edge is disjoint from all the others, so choosing one edge deletes only that edge, and the algorithm takes all edges: . Every vertex cover needs a vertex from each of the disjoint edges, so , and one endpoint of each edge is a cover of size . Thus and , the worst case allowed by the theorem.