Chapter 35: Approximation Algorithms: Vertex Cover, TSP, and Set Covering

The vertex cover problem is addressed by APPROX-VERTEX-COVER, which iteratively selects any edge, adds both endpoints to the cover, removes all incident edges, and repeats — producing a 2-approximation because the selected edges form a maximal matching whose size is a lower bound on the optimal cover, guaranteeing |C| ≤ 2|C*|. For the traveling salesperson problem restricted to edge weights satisfying the triangle inequality, APPROX-TSP-TOUR builds a minimum spanning tree, performs a preorder walk, and visits vertices in order of first appearance, yielding a 2-approximation for metric TSP — while the general TSP without the triangle inequality admits no constant-ratio approximation unless P = NP. The greedy set cover algorithm tackles the problem of covering a universe X by repeatedly choosing the subset that covers the most currently uncovered elements, achieving an O(log |X|) approximation ratio bounded by |C*| × ln|X| + 1, applicable in scheduling and facility location. Randomization and LP relaxation offer additional approximation strategies: randomly assigning truth values to 3-CNF-SAT variables with probability one half achieves an expected 8/7-approximation, while the weighted vertex cover problem is solved within a factor of 2 by formulating it as an integer program, relaxing to a linear program, and rounding all fractional variables of at least one half up to one. Finally, the subset-sum problem is addressed by a fully polynomial-time approximation scheme (FPTAS) that uses list trimming to prune values within ε of each other, keeping the solution list polynomial in size and guaranteeing a result within factor 1+ε of optimal in time polynomial in both n and 1/ε — offering a principled trade-off between precision and computational effort.