COMPX270 — Chapter 10 Supplement
Mathematical Foundations: LP & Rounding
AM-GM inequality, concavity, approximation ratios, and the \(1-1/e\) limit.
AM-GM Inequality
For any non-negative reals \(a_1, \ldots, a_k \geq 0\):
\[\sqrt[k]{a_1 a_2 \cdots a_k} \leq \frac{a_1 + a_2 + \cdots + a_k}{k}\]Geometric mean \(\leq\) Arithmetic mean. Equality iff all \(a_i\) are equal.
We need to relate the product (probability that a clause is not satisfied) to the sum (LP constraint). AM-GM bridges this gap:
\[\prod_{i: x_i \in C_j}(1-y_i^*) \cdot \prod_{i: \neg x_i \in C_j} y_i^* \leq \left(\frac{\sum(1-y_i^*) + \sum y_i^*}{\ell_j}\right)^{\ell_j} = \left(1 - \frac{z_j^*}{\ell_j}\right)^{\ell_j}\]Concavity & Jensen’s Inequality
A function \(f\) is concave on \([a, b]\) if for all \(x, y \in [a,b]\) and \(\lambda \in [0,1]\):
\[f(\lambda x + (1-\lambda)y) \geq \lambda f(x) + (1-\lambda) f(y)\]A concave function lies above its chords. If \(f(a) = 0\), then \(f(x) \geq \frac{f(b)}{b-a}(x-a)\) for \(x \in [a,b]\).
This function appears in the Max-SAT proof. It is concave on \([0,1]\) with \(f(0) = 0\) and \(f(1) = 1 - (1-1/\ell)^\ell\). By concavity:
\[f(z) \geq \left(1 - \left(1 - \frac{1}{\ell}\right)^\ell\right) z \geq \left(1 - \frac{1}{e}\right) z\]Approximation Ratios
For a maximisation problem, an algorithm gives an \(\alpha\)-approximation if for every instance \(I\):
\[\alpha \cdot \text{opt}(I) \leq \mathbb{E}[\text{val}(S)] \leq \text{opt}(I)\]where \(S\) is the output solution and \(0 < \alpha \leq 1\). The closer \(\alpha\) is to 1, the better.
We typically prove \(\mathbb{E}[\text{val}] \geq \alpha \cdot \text{opt}_{LP}\). Since \(\text{opt}_{LP} \geq \text{opt}_{ILP} = \text{opt}\), this gives an \(\alpha\)-approximation. The LP optimum serves as an upper bound proxy for the true optimum.
The \(1 - 1/e\) Limit
The sequence \((1 - 1/\ell)^\ell\) increases towards \(1/e\) as \(\ell \to \infty\):
\[\lim_{\ell \to \infty} \left(1 - \frac{1}{\ell}\right)^\ell = \frac{1}{e} \approx 0.368\]Therefore \(1 - (1-1/\ell)^\ell \geq 1 - 1/e \approx 0.632\) for all \(\ell \geq 1\). This is tight: for \(\ell = 1\), \(1 - (1-1/1)^1 = 1\); as \(\ell \to \infty\), it approaches \(1 - 1/e\).
Math quiz
Chapter math quizzes are in the Quiz Hub. Filter by this chapter and choose Study / Math / All.