# CS261 Lecture14: Algorithms in Bipartite Graphs

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

# CS261 Lecture 4: TSP and Set Cover

In which we describe a ${1.5}$-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 ${X}$ and a symmetric distance function ${d: X \times X \rightarrow {\mathbb R}_{\geq 0}}$ that satisfies the triangle inequality, find a multi-set of edges such that ${(X,E)}$ is a connected multi-graph in which every vertex has even degree and such that ${\sum_{(u,v)\in E} d(u,v)}$ is minimized.

Our idea will be to construct ${E}$ by starting from a minimum-cost spanning tree of ${X}$, and then adding edges so that every vertex becomes of even degree.

But how do we choose which edges to add to ${T}$?