35.4-1

Show that even if we allow a clause to contain both a variable and its negation, randomly setting each variable to 1 with probability $1 / 2$ and to $0$ with probability $1 / 2$ still yields a randomized $8 / 7$-approximation algorithm.

(Omit!)

35.4-2

The MAX-CNF satisfiability problem is like the $\text{MAX-3-CNF}$ satisfiability problem, except that it does not restrict each clause to have exactly $3$ literals. Give a randomized $2$-approximation algorithm for the $\text{MAX-CNF}$ satisfiability problem.

(Omit!)

35.4-3

In the $\text{MAX-CUT}$ problem, we are given an unweighted undirected graph $G = (V, E)$. We define a cut $(S, V - S)$ as in Chapter 23 and the weight of a cut as the number of edges crossing the cut. The goal is to find a cut of maximum weight. Suppose that for each vertex $v$, we randomly and independently place $v$ in $S$ with probability $1 / 2$ and in $V - S$ with probability $1 / 2$. Show that this algorithm is a randomized $2$-approximation algorithm.

(Omit!)

35.4-4

Show that the constraints in line $\text{(35.19)}$ are redundant in the sense that if we remove them from the linear program in lines $\text{(35.17)}–\text{(35.20)}$, any optimal solution to the resulting linear program must satisfy $x(v) \le 1$ for each $v \in V$.

(Omit!)