The Committee's Wishes

Part A: fair coins

A wish whose $k$ conditions are on different decisions fails only when all $k$ coins go against it, with probability $2^{-k}$. So the expected weight met is $3·\frac{3}{4}+2·\frac{3}{4}+4·\frac{7}{8}+1·\frac{1}{2}+2·\frac{7}{8}+3·\frac{1}{2}$, which is 11 out of 15. Here all 15 can be met, for example with $x_1$ yes, $x_2$ no, $x_3$ yes and $x_4$ yes, so the coins lose a quarter. Fair coins always meet at least half the total weight (Johnson, 1974), and more when every wish is long. Single-condition wishes are their weak spot.

Part B: four wishes no choice can meet together

Take every two-condition wish on $x_1$ and $x_2$: "$x_1$ or $x_2$", "not $x_1$ or $x_2$", "$x_1$ or not $x_2$", "not $x_1$ or not $x_2$". Each choice of $x_1,x_2$ fails exactly one of them, so the best is 3. The LP sets $y_1=y_2=\frac{1}{2}$, which gives every wish $z=1$ and a total of 4. The ratio is $\frac{4}{3}\ge \frac{5}{4}$. Two copies on $x_3,x_4$ give the same ratio with 8 wishes.

So no rounding of this LP can promise more than $\frac{3}{4}$ of the LP's value: here even the best real decisions get only $\frac{3}{4}$.

Part C: two roundings that fail, and two that work

• Fair coins meet a single-condition wish with probability $\frac{1}{2}$, even when the LP is sure of it ($y=1$, $z=1$). That is only half of $z$.
• $p=y$ meets a wish with $k$ conditions at $y=\frac{1}{k}$ each with probability $1-(1-\frac{1}{k}{)}^k$. That is $\frac{19}{27}\approx 0.704$ for $k=3$, and it falls towards $1-\frac{1}{e}\approx 0.632$ as $k$ grows.

They fail in opposite places, so combine them.

• Mix them. With probability $\frac{1}{2}$ use fair coins, otherwise use $p=y$ (Goemans and Williamson). A wish with $k$ conditions is met with probability at least $\frac{1}{2}(1-2^{-k})z+\frac{1}{2}(1-(1-\frac{1}{k}{)}^k)z$. That is $\frac{3}{4}z$ for $k=1$ and $k=2$, and at least $0.78z$ for every larger $k$.
• Lean towards $y$, halfway. Set $p_i=\frac{1}{4}+\frac{y_i}{2}$. One vector, no mixture, and part D proves that it also reaches $\frac{3}{4}$.

Testing is not proof. The grader computes your rounding's exact expectation on nine committees and also samples it. Passing shows the $\frac{3}{4}$ holds on those nine. That it holds on every committee needs the argument below.

Part D: why $\frac{1}{4}+\frac{y}{2}$ reaches three quarters

Take a wish with $k$ conditions. Replace $x_i$ by its negation wherever the wish wants "no", so that every condition is "yes". The rounding treats a negated decision the same way, since $1-(\frac{1}{4}+\frac{y}{2})=\frac{1}{4}+\frac{1-y}{2}$. Let the conditions' LP values add up to $s$, so $z=min(1,s)$. The wish fails with probability ${\prod }_i(\frac{3}{4}-\frac{y_i}{2})\le (\frac{3}{4}-\frac{s}{2k}{)}^k$, by the inequality of arithmetic and geometric means. So it is met with probability at least $g(s)=1-(\frac{3}{4}-\frac{s}{2k}{)}^k$.

• If $s\ge 1$: $g(s)\ge g(1)=1-(\frac{3}{4}-\frac{1}{2k}{)}^k$. That is $\frac{3}{4}$ for $k=1$ and $k=2$, and $(\frac{3}{4}-\frac{1}{2k}{)}^k\le (\frac{7}{12}{)}^3<\frac{1}{4}$ for $k\ge 3$.
• If $s<1$: $g$ is concave, $g(0)\ge 0$ and $g(1)\ge \frac{3}{4}$, so $g(s)\ge s·g(1)\ge \frac{3}{4}s$.

Adding over the wishes, the expected weight met is at least $\frac{3}{4}{\sum }_C{w}_C{z}_C$. Part B shows that $\frac{3}{4}$ is the best any rounding of this LP can promise. Conditional expectations turn the rounding into a deterministic algorithm: fix the decisions one at a time, each time keeping the choice with the larger conditional expectation.

Going further

• Semidefinite programming. Goemans and Williamson's SDP rounding meets $0.878$ of the optimum for MAX-2-SAT, beyond what any rounding of this LP can promise. The best known ratios for MAX-SAT in general are close to $0.8$.
• The limit. For MAX-3-SAT, where every wish has exactly three conditions, fair coins already meet $\frac{7}{8}$, and Håstad proved that no polynomial-time algorithm does better unless P = NP.
• Rounding in general. Raghavan and Thompson introduced randomized rounding for packing and routing problems. Set cover, facility location and Steiner tree (Approximation Algorithms) all have rounding algorithms of this kind.

References

1. D. S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9(3), 1974.
2. P. Raghavan, C. D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 1987.
3. M. X. Goemans, D. P. Williamson. New 3/4-approximation algorithms for the maximum satisfiability problem. SIAM Journal on Discrete Mathematics 7(4), 1994.
4. M. X. Goemans, D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42(6), 1995.
5. J. Håstad. Some optimal inapproximability results. Journal of the ACM 48(4), 2001.
6. D. P. Williamson, D. B. Shmoys. The Design of Approximation Algorithms, chapter 5. Cambridge University Press, 2011.