Set Cover | in theory

In which we show how to round a linear programming relaxation in order to approximate the set cover problem, and we show how to reason about the dual of the relaxation to derive a simple combinatorial approximation algorithm for the weighted case.

Recall that in Set Cover we are given a finite set ${U}$ and a collection ${S_1,\ldots,S_n}$ of subsets of ${U}$ . We want to find the fewest sets whose union is ${U}$ , that is, the smallest ${I\subseteq \{1,\ldots,n \}}$ such that ${\bigcup_{i\in I} S_i = U}$ .

We described an algorithm whose approximation guarantee is ${\ln |U|+ O(1)}$ . The lower bound technique that we used in our analysis was to realize that if we have a subset ${D\subseteq U}$ of elements, such that every set ${S_i}$ contains at most ${t}$ elements of ${D}$ , then ${opt \geq |D|/t}$ .

Today we will describe a linear programming relaxation of set cover, and we will show a way to round it, in order to achieve an ${O(\log |U|)}$ approximation.

We will also show that the lower bounds to the optimum that we used in the analysis of the greedy algorithm can also be expressed as feasible solutions for the dual of our linear programming relaxation.

Continue reading →

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}$ ?

Continue reading →

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

Tag Archives: Set Cover

CS261 Lecture 8: Randomized Rounding

CS261 Lecture 4: TSP and Set Cover