Approximations

Set Cover

Here is the Set-Cover problem. You are given a set

E = {e_{1}, \dots, e_{n}}

, and

m

subsets

S_{1}, \dots, S_{m} \subseteq E

. For each

j \in [m]

, we associate a weight

w_{j} \geq 0

to the set

S_{j}

. The goal is to find a minimum-weight collection of subsets that covers all of

E

Form the set-cover problem as an integer linear program, and then relax it to a linear program. Define your variables. [Hint: you might want to have a constraint like $\sum_{j : e_{i} \in S_{j}} x_{j} \geq 1$ for each element $e_{i}$ .]
Let $x^{*}$ denote the optimal solution to the relaxed LP you defined in part (a). Let $f$ be the maximum number of subsets in which any element appears. Here's the rounding algorithm: given $x^{*}$ , we include $S_{j}$ if and only if $x_{j}^{*} \geq 1 / f$ . Let $I = {j : S_{j}$ is selected by the rounding algorithm $}$ . Prove that the collection of subsets $S_{j}$ where $j \in I$ chosen by the rounding algorithm is a set cover.
Let OPT be value of the optimal solution of the set-cover. Prove that the rounding algorithm in (b) gives an $f$ -approximation.

Let's first define the linear integer program as follows for each

S_{j}

lets define

x_{S_{j}}

to be either the value

0

1

where this varaible represents whether or not we use

S_{j}

in our collection of subsets that cover

E

. With that in place our goal will be to minimize

\sum_{S_{i} \in S} w_{i} x_{S_{i}}

which represents the weighted sum of our selected subsets. We will also enforce that

e_{k}

is in a least one of these subsets, so let

I_{k}

be the collection of subsets that

e_{k}

is in and thus for each

k \in [1 \dots n]

we enforce the constraint:

\sum_{S_{i} \in I_{k}} x_{S_{i}} \geq 1

We can now relax the problem by allowing $x_{S_{i}} \in ℝ^{\geq 0}$

We now prove that the selection of subsets selected using the rounding algorithm is a set cover. Given an $e_{k}$ , lets show that there is some $S_{m}$ such that $e_{k} \in S_{m}$ where $S_{m}$ has been selected using the rounding algorithm.

When know that $e_{k}$ is included in at most (or equal to) $f$ subsets, therefore we know that what this means is that $| I_{k} | \leq f$ therefore since the solution still respects the constraint: $\sum_{S_{i} \in I_{k}} x_{S_{i}} \geq 1$ then if each $x_{S_{i}} < \frac{1}{f}$ then the sum would be less than 1 which is a contradiction, therefore there is at least one $i$ such that $x_{S_{i}} \geq \frac{1}{f}$ , by construction our round algorithm will select $S_{i}$ , on the other hand $S_{i} \in I_{k}$ and therefore $e_{k} \in S_{i}$ so $e_{k}$ is covered, since this holds for any $k$ the entire collection $E$ is covered.

Note that $OPT = \sum w_{i} x_{i}$ and suppose that the optimal solution from the relaxation is given by $\sum w_{i} y_{i}$ where the $y_{i}$ are used to differentiate from the OPT solution, let the solution given by taking the optimal relaxation solution and doing rounding be given by $\sum w_{i} r (y_{i})$ where $r$ maps to 0 if the value is less than $\frac{1}{f}$ and 1 otherwise.

Let's now observe a few relationships between these solutions. First note that by relaxing a binary varaible it allows for the binary values to be taken on, but also other values, within these new possible values we may be able to find a solution which yields a better objective value. Thus we have $\sum w_{i} x_{i} \geq \sum w_{i} y_{i}$ .Note that if $y_{i} \geq \frac{1}{f}$ then we know that $r (y_{i}) = 1$ and so there is some $α_{i} \leq f$ such that $α y_{i} = r (y_{i})$ , at the same time if $y_{i} < \frac{1}{f}$ then $r (y_{i}) = 0 = f 0$ thus we have $\sum w_{i} r (y_{i}) = \sum w_{i} (α x_{i}) \leq \sum w_{i} (f x_{i}) = f \sum w_{i} x_{i} = f \cdot OPT$ simply: $\sum w_{i} r (y_{i}) \leq f \cdot OPT$ as needed.

Metric TSP

Here's the metric traveling salesman problem. You are given a complete graph $G = (V, E)$ , where $V = {1, \dots, n}$ represents the cities the salesman needs to visit. For each edge $(i, j) \in E$ , we associate it with a cost $c_{i j}$ . We call it "metric" because for every triplet of vertices $i, j, k \in V$ , it respects the triangle inequality, i.e. $c_{i k} \leq c_{i j} + c_{j k}$ .

The goal is to have a tour of the cities (i.e. a Hamiltonian cycle of $G$ ) such that each city is visited exactly once (except for the starting city where you have to come back to), and the total cost is minimized.

Here is our approximation algorithm, which is also a greedy algorithm: Among all pairs of cities, find the two closest cities, say $i$ and $j$ , and start by building a tour on that pair of cities; the tour consists of going from $i$ to $j$ and then back to $i$ again. This is the first iteration. In each subsequent iteration, we extend the tour on the current subset $S \subseteq V$ by including one additional city, until we include the full set of cities. Specifically in each iteration, we find a pair of cities $i \in S$ and $j \notin S$ for which the cost $c_{i j}$ is minimum; let $k$ be the city that follows $i$ in the current tour on $S$ . We add $j$ to $S$ , and replace the path $i \to k$ with $i \to j$ and $j \to k$ . See the picture below for illustration:

Let OPT be the value of the optimal solution of the metric traveling salesman problem. Prove that the approximation algorithm above gives a 2-approximation.

Firstly observe that the specified algorithm is very similar to Prim's algorithm, which generates a minimal spanning tree. We make the followign claim at iteration $k$ the cost subtour constructed by the approximation algorithm is less than or equal to 2 times the cost of the sub-spanning tree constructed by prim's algorithm. Let $A_{i}$ and $P_{i}$ denote the cost at iteration of $i$ of the approximation and prim's algorithm respectively.

Base case: On the first iteration the approximation algorithm selects the two vertices that are closest together ( $i, j$ ) and constructs the tour $i - j - i$ this cost is equal to $d (i, j) + d (j, i)$ , on the other hand the subtree constructed by prim is simply $i - j$ and therefore it's cost is only $d (i, j)$ so we have that $A_{i} = 2 P_{i} \leq 2 P_{i}$ as needed.

Induction Step: Assume that the statement holds true for $k \in ℕ_{1}$ and lets show it holds true for $k + 1$ . At iteration $k + 1$ since the pseudocode of the approximation algorithm selects the next vertex in the same way a prim, they both select some new vertex $v_{m}$ where this vertex forms the smallest distance with respect to all of the vertices which have been selected already (which is also the same for both algorithms at this iteration). Suppose this smallest distance was observed with the pair $v_{a} \in S$ , which is to say that $d (v_{a}, v_{m})$ was minimized.

Recall that the approximation states that it will remove the vertex after $v_{a}$ in the tour (which we will denote as $v_{b}$ ) and then inserts $v_{a} - v_{m} - v_{b}$ instead. The increase in cost by doing so is equal to $d (v_{a}, v_{m}) + d (v_{m}, v_{b}) - d (v_{a}, v_{b})$ , now we remark the following $d (v_{m}, v_{b}) \leq d (v_{m}, v_{a}) + d (v_{a}, v_{b}) = d (v_{a}, v_{m}) + d (v_{a}, v_{b})$ therefore $d (v_{a}, v_{m}) + d (v_{m}, v_{b}) - d (v_{a}, v_{b}) \leq 2 d (v_{a}, v_{m})$ Keep remembering that this edge $v_{a}, v_{m}$ is the exact same edge that prim will have chosen at iteration $k + 1$ because both of these algorithms select their next vertices in the same manner. Thus we have $\begin{matrix} A_{k + 1} & = A_{k} + (d (v_{a}, v_{m}) + d (v_{m}, v_{b}) - d (v_{a}, v_{b})) \\ \leq 2 \cdot P_{k} + (d (v_{a}, v_{m}) + d (v_{m}, v_{b}) - d (v_{a}, v_{b})) \\ \leq 2 \cdot P_{k} + 2 d (v_{a}, v_{m}) \\ = 2 (P_{k} + d (v_{a}, v_{m})) \\ = 2 P_{k + 1} \end{matrix}$ Thus the induction step is proven.

What we can infer is that after both algorithms terminate on the same iteration, the approximation algorithm has created a tour $T$ and prim has created a minimal spanning tree $M$ such that $c (T) \leq 2 c (M)$ . Now note that given a minimal spanning tree we know that it's cost is always going to be less than or equal to OPT, this is because by removing a single edge from OPT which is a tour, we obtain a spanning tree whose cost is less than or equal to the cost of the tour, but also it's a spanning tree and so the minimal spanning tree will have cost less than or equal to it, so now we have that $c (T) \leq 2 c (M) \leq 2 O P T$ hence the approximation algorithm yields a 2-approximation.

Randomized Max Cut

Let

G = (V, E)

be an undirected graph. For any subset of vertices

U \subseteq V

, define

cut (U) = {(u, v) \in E : u \in U and v \notin U} .

The set $cut (U)$ is called the cut determined by the vertex set $U$ . The size of the cut is denoted by $| cut (U) |$ . The Max-Cut problem asks you to find the cut with maximum size, i.e., $\max_{U \subseteq V} | cut (U) |$ .

Here is a randomized algorithm for Max-Cut: Take a uniform random subset $U$ of $V$ , and choose $cut (U)$ to be the cut. Let OPT be the size of the maximum cut in $G$ .

Prove that the randomized algorithm gives a cut of expected size at least half of the optimal solution, i.e.,

𝔼 [| cut (U) |] \geq \frac{1}{2}

OPT.

In order to solve this we must know the meaning of a uniform random subset $U$ of $V$ , to select a uniform random subset means that there is equal probability for a given vertex to either be in $U$ or for it to not be in $U$ , what this means is that given any $e \in E$ we have that $P (e \in cut (U)) = \frac{1}{2}$ , observe that we have the indicator function $I_{C} : E (U) \to {0, 1}$ which equals $1$ when an edge is in the cut and 0 when it is not, and that the indicator function can be thought of as a random variable.

Note that $| cut (U) | = \sum_{e \in E} I_{C} (e)$ , since expected value is linear then we know $E (| cut (U) |) = \sum_{e \in E} E (I_{C} (e))$

Now let's note that for a given fixed $e^{⋆}$ we know that $E (I_{C} (e^{⋆})) : = P (I_{C} (e^{⋆}) = 1) 1 + P (I_{C} (e^{⋆}) = 0) 0 = \frac{1}{2}$ therefore we continue the chain of equalities from our previous paragraph obtaining: $\sum_{e \in E} E (I_{C} (e)) = \frac{| E |}{2}$

Note that the size of the cut is clearly upperbounded by how many edges your graph actually has, so that $\frac{| E |}{2} \geq \frac{OPT}{2}$ thus connecting everything we obtain that $E (| cut (U) |) \geq \frac{OPT}{2}$ as needed.

Randomized Max-k-Sat

Max-

k

-SAT is a problem where we try to maximize the number of clauses that can be satisfied. Suppose there are

n

variables

x_{1}, x_{2}, \dots, x_{n}

, and each clause contains precisely

k

distinct literals (e.g.

({\overline{x}}_{1} \lor x_{2} \lor {\overline{x}}_{3} \lor \dots \lor x_{k})

), and

x_{i}

and

{\overline{x}}_{i}

will not both appear in the same clause. Note that unlike Exact-

k

-SAT, we do not demand that every clause to be satisfied.

Prove that there exists a randomized algorithm that will approximately solve Max $k$ -SAT within an approximation ratio of $(2^{k} - 1) / 2^{k}$ .
Provide a de-randomization of the algorithm that uses the method of conditional expectations.

Our randomized algorithm simply assigns random truth values to all variables, since each clause is a sequence of logical or operations taken at once and it uses $k$ distinct variables, then there is exactly one way for it to be false, and $2^{k}$ possible truth assigments to these variables, therefore the probability that the whole statement is true is given by $\frac{2^{k} - 1}{2^{k}}$

If there are $m$ clauses total, then the expected number of satisfied clauses is simply given by $m \cdot \frac{2^{k} - 1}{2^{k}}$ , since the optimal number of satisfied clauses is $m$ then this provides a $\frac{2^{k} - 1}{2^{k}}$ approximation.

Note that if our random assigment doesn't yield a solution that satisfies at least $\frac{2^{k} - 1}{2^{k}} m$ clauses, we simply try a new random assignment, it should only take a few iterations until we do at least as well as the expected value.