In which we show how to solve the maximum matching problem and the minimum vertex cover problem in bipartite graphs.
In which we describe a -approximate algorithm for the Metric TSP, we introduce the Set Cover problem, observe that it can be seen as a more general version of the Vertex Cover problem, and we devise a logarithmic-factor approximation algorithm.
1. Better Approximation of the Traveling Salesman Problem
In the last lecture we discussed equivalent formulations of the Traveling Salesman problem, and noted that Metric TSP-R can also be seen as the following problem: given a set of points and a symmetric distance function that satisfies the triangle inequality, find a multi-set of edges such that is a connected multi-graph in which every vertex has even degree and such that is minimized.
Our idea will be to construct by starting from a minimum-cost spanning tree of , and then adding edges so that every vertex becomes of even degree.
But how do we choose which edges to add to ?