COMPX270 — Randomised and Advanced Algorithms
Chapter 10: Linear Programming & Randomised Rounding
LP relaxation of ILPs, randomised rounding for Min-Cut, Max-SAT approximation algorithms achieving \(\frac{1}{2}\), \(1-\frac{1}{e}\), and \(\frac{3}{4}\) ratios.
Linear Programming (LP)
Standard Form
A Linear Program maximises a linear objective subject to linear constraints:
\[\text{maximise } c^\top x \quad \text{subject to } Ax \leq b, \; x \geq 0\]where \(x \in \mathbb{R}^n\) are variables, \(c \in \mathbb{R}^n\) the objective, \(A \in \mathbb{R}^{m \times n}\) and \(b \in \mathbb{R}^m\) encode constraints.
Integer Linear Programs (ILP)
From LP to ILP
An ILP adds integrality constraints: \(x_i \in \{0, 1\}\) (or \(\mathbb{Z}\)). This allows encoding NP-hard problems like Max-Cut, Max-SAT, and Knapsack.
Example: st-Min-Cut as ILP
Variables: \(x_e \in \{0,1\}\) (edge in cut?), \(y_v \in \{0,1\}\) (vertex on sink side?).
\[\text{minimise } \sum_{e \in E} c_e x_e \quad \text{s.t. } y_s = 0, \; y_t = 1, \; y_v \leq y_u + x_e \;\forall e=(u,v)\]LP Relaxation
The Key Idea
Replace the hard constraint \(x_i \in \{0,1\}\) with \(x_i \in [0, 1]\). This converts the ILP into an LP we can solve efficiently.
Fact 45.1: LP Relaxation Bound
For a maximisation ILP and its LP relaxation:
\[\text{opt}_{ILP} \leq \text{opt}_{LP}\]The LP relaxation over-estimates the optimal (for maximisation). For minimisation, the inequality reverses.
Randomised Rounding for Min-Cut
Algorithm 21: Randomised Rounding for Min-Cut LP
- Solve the LP relaxation to get optimal \((x^*, y^*)\).
- Pick \(\tau \in (0, 1)\) uniformly at random.
- For each \(v \in V\): set \(y_v = 1\) if \(y_v^* > \tau\), else \(y_v = 0\).
Theorem 46
The cut \(y\) returned by Algorithm 21 satisfies \(\mathbb{E}[\text{val}(y)] = \text{opt}_{ILP}\).
Moreover, since \(\text{val}(y) \geq \text{opt}_{MinCut}\) always (it is a valid cut), and the expectation equals the optimum, we must have \(\text{val}(y) = \text{opt}_{MinCut}\) with probability 1!
By linearity of expectation:
\[\mathbb{E}[\text{val}(y)] = \sum_{e=(u,v) \in E} c_e \Pr[y_u = 0, y_v = 1]\]For edge \(e = (u,v)\): \(\Pr[y_u = 0, y_v = 1] = \Pr[y_u^* \leq \tau < y_v^*] \leq y_v^* - y_u^* \leq x_e^*\) (by LP constraint).
Therefore \(-\mathbb{E}[\text{val}(y)] \leq \sum c_e x_e^* = -\text{opt}_{LP} \leq -\text{opt}_{ILP}\). \(\square\)
Max-SAT Approximation
The Max-SAT Problem
\(n\) Boolean variables \(x_1, \ldots, x_n\), \(m\) clauses \(C_1, \ldots, C_m\). Each clause is a disjunction (OR) of literals. Goal: maximise the number of satisfied clauses. NP-Hard.
Theorem 47: Naive Random — \(\frac{1}{2}\)-approximation
Set each \(x_i = 1\) independently with probability \(\frac{1}{2}\). Then:
\[\mathbb{E}[\text{val}(x)] = \sum_{j=1}^{m} \left(1 - \frac{1}{2^{\ell_j}}\right) \geq \frac{m}{2} \geq \frac{1}{2}\text{opt}(\varphi)\]For Max-E3SAT (all clauses have 3 literals): this gives a \(\frac{7}{8}\)-approximation!
ILP Formulation for Max-SAT
Variables: \(y_i \in \{0,1\}\) for Boolean variables, \(z_j \in \{0,1\}\) for clause satisfaction.
\[\text{maximise } \sum_{j=1}^{m} z_j \quad \text{s.t. } \sum_{i: x_i \in C_j} y_i + \sum_{i: \neg x_i \in C_j} (1 - y_i) \geq z_j, \;\; y_i, z_j \in \{0,1\}\]Theorem 48: LP Rounding — \((1-1/e)\)-approximation
Solve the LP relaxation to get \((y^*, z^*)\). Set \(x_i = 1\) w.p. \(y_i^*\) independently. Then:
\[\mathbb{E}[\text{val}(x)] \geq \left(1 - \frac{1}{e}\right)\text{opt}_{LP} \geq \left(1 - \frac{1}{e}\right)\text{opt}(\varphi) \approx 0.632 \cdot \text{opt}(\varphi)\]Uses the AM-GM inequality to relate the product (probability of failure) to the sum (LP constraint).
For clause \(C_j\) with \(\ell_j\) literals, by independence and AM-GM:
\[\Pr[C_j \text{ not sat}] = \prod_{i: x_i \in C_j}(1-y_i^*) \cdot \prod_{i: \neg x_i \in C_j} y_i^* \leq \left(1 - \frac{z_j^*}{\ell_j}\right)^{\ell_j}\]The function \(f(z) = 1 - (1-z/\ell)^\ell\) is concave, so \(f(z) \geq (1-(1-1/\ell)^\ell) z\). Since \(\sup_{\ell \geq 1}(1-1/\ell)^\ell = 1/e\):
\[\mathbb{E}[\text{val}] \geq \sum_j (1-1/e) z_j^* = (1-1/e) \cdot \text{opt}_{LP} \qquad \square\]Interactive: Max-SAT Approximation Demo
Generate a random 3-SAT instance and compare the three algorithms.
The \(\frac{3}{4}\)-Approximation: Best-of-Two
Theorem 49
Run both the naive random algorithm and the LP rounding. Return the better solution. This gives, in expectation, a \(\frac{3}{4}\)-approximation for Max-SAT.
\[\mathbb{E}[\max(\text{val}(x), \text{val}(x'))] \geq \frac{3}{4} \cdot \text{opt}(\varphi)\]Since \(\max \geq \text{average}\):
\[\mathbb{E}[\max(\text{val}(x), \text{val}(x'))] \geq \frac{1}{2}\left(\sum_j\left(1-\frac{1}{2^{\ell_j}}\right) + \sum_j\left(1-\left(1-\frac{1}{\ell_j}\right)^{\ell_j}\right)z_j^*\right)\]The key inequality: for every \(\ell \geq 1\) (integer):
\[\left(1 - \frac{1}{2^\ell}\right) + \left(1 - \left(1-\frac{1}{\ell}\right)^\ell\right) \geq \frac{3}{2}\]This gives \(\mathbb{E}[\max] \geq \frac{1}{2} \cdot \frac{3}{2}\sum_j z_j^* = \frac{3}{4}\text{opt}_{LP} \geq \frac{3}{4}\text{opt}(\varphi)\). \(\square\)
Tutorial Problems
Problem 1 Warm-up
Recall the definitions of LP and ILP, and summarise the key differences.
LP: Optimise a linear function subject to linear constraints on continuous domain. P-complete, efficiently solvable.
ILP: LP with integrality constraints (e.g., \(x_i \in \{0,1\}\)). More expressive (can encode NP-hard problems), but hard to solve in general. \(\square\)
Problem 2 Warm-up
(a) Formulate Max-Cut as an ILP and give its LP relaxation.
(b) Show that \(y^* = (1,\ldots,1)\) and \(x^* = (1/2,\ldots,1/2)\) is always optimal for the LP relaxation.
(c) What does randomised rounding become with this solution?
(a) Maximise \(\sum_{e \in E} w_e y_e\) subject to \(y_e \leq x_u + x_v\) and \(y_e \leq 2 - (x_u + x_v)\) for all \(e = (u,v)\), with \(x_v, y_e \in \{0,1\}\). Relax to \([0,1]\).
(b) With \(x^* = (1/2, \ldots, 1/2)\), every constraint \(y_e \leq x_u + x_v = 1\) and \(y_e \leq 2 - 1 = 1\) is satisfied, allowing \(y_e^* = 1\) for all edges. Value = \(\sum w_e\), the maximum possible.
(c) Setting \(v \in S\) w.p. \(x_v^* = 1/2\) independently is just the simple random algorithm! LP relaxation gives nothing new for Max-Cut. \(\square\)
Problem 3 Warm-up
Describe how to derandomise the \(\frac{3}{4}\)-approximation for Max-SAT.
Use the method of conditional expectations on both algorithms separately. For the naive algorithm: iterate through \(x_1, \ldots, x_n\), choosing the value that maximises the conditional expectation. For the LP rounding: same approach using \(y_i^*\) as the probability. Take the best of the two deterministic solutions. \(\square\)
Problem 4 Problem Solving ⭐
Consider the Knapsack problem: \(n\) items, weight limit \(W\), item \(i\) has value \(v_i\) and weight \(w_i\).
(a) Give the ILP. (b) LP relaxation. (c-e) Solve numerically for \((v_i, w_i) = (i^2, i)\), \(W = 20\).
(a) Maximise \(\sum_i v_i x_i\) s.t. \(\sum_i w_i x_i \leq W\), \(x_i \in \{0,1\}\).
(b) Relax to \(x_i \in [0,1]\). The LP solution is the same as greedy fractional knapsack: sort by \(v_i/w_i\) (here \(v_i/w_i = i\)), pack from largest ratio. For \(W=20\): take items 10, 9 (weight 19), then 0.125 of item 8. LP value = 181.125, ILP optimum = 182 (items 1, 9, 10). \(\square\)
Problem 5 Problem Solving ⭐
For Max-SAT with no negated unit clauses, set each variable to 1 with probability \(p > 1/2\).
(a) Show this gives a \(\min(p, 1-p^2)\)-approximation.
(b) Find the optimal \(p\).
(a) Unit clause (non-negated): satisfied w.p. \(p\). Clause of length \(\ell \geq 2\) with \(a\) negated, \(b\) non-negated variables: not satisfied w.p. \(p^a(1-p)^b < p^{a+b} \leq p^2\). So each clause is satisfied w.p. \(\geq \min(p, 1-p^2)\).
(b) Setting \(p = 1 - p^2\) gives \(p = \frac{\sqrt{5}-1}{2} \approx 0.618\), the golden ratio minus 1. This gives a 0.618-approximation (slightly worse than \(1-1/e \approx 0.632\)). \(\square\)
Problem 6 Problem Solving ⭐
Show a direct \(\frac{3}{4}\)-approximation via modified rounding: \(p_i = f(y_i^*)\) where \(1 - 1/4^x \leq f(x) \leq 1/4^{1-x}\).
(b) Show \(\Pr[C_j \text{ not sat}] \leq 1/4^{z_j^*}\). (c) Deduce \(\Pr[C_j \text{ sat}] \geq \frac{3}{4}z_j^*\).
(b) \(\Pr[\text{not sat}] = \prod_{i: x_i \in C_j}(1-f(y_i^*)) \cdot \prod_{i: \neg x_i \in C_j}f(y_i^*) \leq \prod 1/4^{y_i^*} \cdot \prod 1/4^{1-y_i^*} = 4^{-z_j^*}\).
(c) Since \(g(x) = 1 - 1/4^x\) is concave and \(g(0) = 0\): \(\Pr[\text{sat}] \geq 1 - 1/4^{z_j^*} \geq z_j^* \cdot g(1) = \frac{3}{4}z_j^*\).
Summing: \(\mathbb{E}[\text{val}] \geq \frac{3}{4}\sum z_j^* \geq \frac{3}{4}\text{opt}(\varphi)\). \(\square\)
Problem 7 Advanced ⭐⭐
Show a direct \(\frac{3}{4}\)-approximation using the linear rounding: \(p_i = y_i^*/2 + 1/4\).
This is a specific \(f\) that satisfies the bounds in Problem 6: \(f(x) = x/2 + 1/4\). Verify: \(f(0) = 1/4 = 1/4^1\) and \(f(1) = 3/4 = 1 - 1/4^1\). The bounds hold because the linear function lies between the two curves. The same analysis as Problem 6 applies. \(\square\)
Chapter quizzes
Self-test and math questions for this chapter are in the Quiz Hub (practice or exam mode).