跳转至

35.4 Randomization and linear programming

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.

\(\gdef\Ex{\mathbf{E}}\) \(\gdef\Prob{\mathbf{P}}\) \(\gdef\opt{\texttt{opt}}\)

We first rewrite the algorithm for clarity.

C++
1
2
3
4
5
6
7
APPROX-MAX-CUT(G)
    for each v in V
        flip a fair coin
        if heads
            add v to S
        else
            add v to V - S

This algorithm clearly runs in linear time. For each edge \((u, v) \in E\), define the event \(A_{uv}\) to be the event where edge \((i, j)\) crosses the cut \((S, V - S)\), and let \(1_{A_{uv}}\) be the indicator random variable for \(A_{uv}\).

The event \(A_{ij}\) occurs if and only if the vertices \(u\) and \(v\) are placed in different sets during the main loop in \(\text{APPROX-MAX-CUT}\). Hence,

\[ \begin{aligned} \Prob \\{A_{uv}\\} &= \Prob \\{u \in S \wedge v \in V - S\\} + P\\{u \in V - S \wedge v\in S\\} \\\\ &= \frac{1}{2}\cdot\frac{1}{2} + \frac{1}{2}\cdot\frac{1}{2} \\\\ &= \frac{1}{2}. \end{aligned} \]

Let \(\opt\) denote the cost of a maximum cut in \(G\), and let \(c = |(S, V - S)|\), that is, the size of the cut produced by \(\text{APPROX-MAX-CUT}\). Clearly \(c = \sum_{(u, v) \in E} 1_{A_{uv}}\). Also, note that \(\texttt{opt} \leq |E|\) (this is tight iff \(G\) is bipartite). Hence,

\[ \begin{aligned} \Ex[c] &= \Ex\left[\sum_{(u, v) \in E} 1_{A_{uv}}\right]\\\\ &= \sum_{(u, v)\in E}\Ex[1_{A_{uv}}]\\\\ &= \sum_{(u, v)\in E}\Prob\\{A_{uv}\\}\\\\ &= \frac{1}{2}|E|\\\\ &\ge \frac{1}{2}\opt \end{aligned} \]

Hence, \(\Ex\left[\frac{\opt}{c}\right] \le \frac{|E|}{1 / 2|E|} = 2\), and so \(\text{APPROX-MAX-CUT}\) is a randomized \(2\)-approximation algorithm.

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!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用