*In which we show how to solve the maximum matching problem and the minimum vertex cover problem in bipartite graphs.*

# Tag Archives: perfect matching

# CS261 Lecture 4: TSP and Set Cover

*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 ?