lecture notes, released on 20. 5. 2022

This post is an expanded translation of my lecture notes from a Randomized and Approximation Algorithms course and is meant to be a more detailed explanation of the topics covered in my upcoming video about BEST-SAT.

Basic definitions

An example problem could be minimum spanning trees:

  • input instances: set of all weighted graphs
  • permissible inputs: spanning trees for the given weighted graph
  • utility function: the spanning tree weight (sum of its edges)
  • we’re minimizing

Definition (Optimalization problem) is a tuple I,F,f,g\mathcal{I}, \mathcal{F}, f, g

Definition (NP-Optimalization problem) is an optimalization problem I,F,f,g\mathcal{I}, \mathcal{F}, f, g, for which we additionally require that:

For minimalization problem, we ensure that the solution is always small enough.

For maximalization problem, we ensure that the solution is always large enough.

Definition: algorithm AA is RR-approximation, if:


We also assume that:


Algorithm (RAND-SAT):

  1. choose all literals randomly (independently, for p=1/2p = 1/2)
  2. profit?

Theorem: RAND-SAT is a 22-approximation algorithm.

Proof: we’ll create an indicator variable YjY_j for each clause

Since the size of the clause k1k \ge 1, we get E[Yj]=Pr[Cj is satistied]=112k12\mathbb{E}\left[Y_j\right] = \mathrm{Pr}\left[C_j\ \text{is satistied}\right] = 1 - \frac{1}{2^k} \ge \frac{1}{2} , thus E[j=1nYj]=linearityof expectationj=1nE[Yj]j=1n1212OPT\mathbb{E}\left[\sum_{j = 1}^{n} Y_j\right] \overset{\text{linearity} \atop \text{of expectation}}{=} \sum_{j = 1}^{n} \mathbb{E}\left[Y_j\right] \ge \sum_{j = 1}^{n}\frac{1}{2} \ge \frac{1}{2}\mathrm{OPT}


We’re using the optimal solution to the linear program (and generally the formula, if we allow real vlaues for literals) as a guide for our randomized algorithm.

Algorithm (LP-SAT):

  1. build an integer linear program:
    • variables will be:
      • yiy_i for each literal
      • zjz_j for each clause
    • inequalitites will be one for each clause, in the form zjpositiveyi+negative(1yi)z_j \le \sum_{\text{positive}} y_i + \sum_{\text{negative}} (1 - y_i)
    • we’ll maximize the number of satisfied clauses zj\sum z_j
  2. relax the program (allow real variables instead of integers) and calculate the optimum y,zy^*, z^*
  3. set literals xix_i to 11 with probability yiy_i^*

Theorem: LP-SAT is a (11e)\left(1 - \frac{1}{e}\right)-approximation algorithm.

To prove this, we’ll use a few lemmas/theorems that aren’t difficult to prove, but aren’t really interesting. I left links to (Wikipedia and I don’t feel bad about it) articles with proofs for each, if you’re interested.

Fact (A - A/G mean inequality): i=1nai1n1ni=1nai\prod_{i = 1}^{n} a_i^{\frac{1}{n}} \le \frac{1}{n} \sum_{i = 1}^{n} a_i


Fact (B - Jensen’s inequality): if a function is concave on the interval [0,1]\left[0, 1\right] and f(0)=a,f(1)=a+bf(0) = a, f(1) = a + b, then x[0,1]:f(x)a+bx\forall x \in \left[0, 1\right]: f(x) \ge a + bx


Fact (C - 1/e inequality): (11n)n1e\left(1 - \frac{1}{n}\right)^n \le \frac{1}{e}


Proof (of the main theorem): consider y,zy^*, z^* and CjC_j with kjk_j literals; then

Pr[Cj is not satisfied]=i: xiCj(1yi)positivei: xiCjyinegativeA[1kj(i: xiCj(1yi)+i: xiCjyi)]kj=[11kj(i: xiCjyi+i: xiCj(1yi))]kj(1zjkj)kj \begin{aligned} \mathrm{Pr}\left[C_j\ \text{is not satisfied}\right] &= \overbrace{\prod_{i:\ x_i \in C_j} (1 - y^*_i)}^{\text{positive}} \overbrace{\prod_{i:\ \overline{x}_i \in C_j} y^*_i}^{\text{negative}} & \\ &\overset{A}{\le} \left[\frac{1}{k_j} \left(\sum_{i:\ x_i \in C_j} (1 - y^*_i) + \sum_{i:\ \overline{x}_i \in C_j} y^*_i\right)\right]^{k_j} & \\ &= \left[1 - \frac{1}{k_j} \left(\sum_{i:\ x_i \in C_j} y^*_i + \sum_{i:\ \overline{x}_i \in C_j} (1 - y^*_i)\right)\right]^{k_j} & \\ &\le \left(1 - \frac{z_j^*}{k_j}\right)^{k_j} \end{aligned}

We’re interested in the satisfied ones, so Pr[Cj is satisfied]1(1zjkj)kjour function f(zj)B[1(11kj)kj]zjC(11e)zj \begin{aligned} \mathrm{Pr}\left[C_j\ \text{is satisfied}\right] &\ge \overbrace{1 - \left(1 - \frac{z_j^*}{k_j}\right)^{k_j}}^{\text{our function}\ f(z_j^*)} \\ & \overset{B}{\ge} \left[1 - \left(1 - \frac{1}{k_j}\right)^{k_j}\right] z_j^* & \overset{C}{\ge} \left(1 - \frac{1}{e}\right) z_j^* \end{aligned}

To use fact BB, we observed that a=f(0)=0a = f(0) = 0 and that the second derivation is non-positive (so the function is concave). Now to formally count how many our program satisfies: E[j=1mYj]=j=1mE[Yj]jUPr[Cj is satisfied]jU(11e)zj=(11e)OPT \begin{aligned} \mathbb{E}\left[\sum_{j = 1}^{m} Y_j\right] &= \sum_{j = 1}^{m} \mathbb{E}\left[Y_j\right] \\ &\ge \sum_{j \in U} \mathrm{Pr}\left[C_j\ \text{is satisfied}\right] \\ &\ge \sum_{j \in U} \left(1 - \frac{1}{e}\right) z_j^* \\ &= \left(1 - \frac{1}{e}\right) \mathrm{OPT}\\ \end{aligned}


Algorithm (BEST-SAT):

  1. assign a value of a literal using RAND-SAT with probability 1/21/2, else use BEST-SAT
  2. have an existential crisis about the fact that this works and is asymptotically optimal

Theorem: BEST-SAT is 34\frac{3}{4}-approximation.

Proof: we want to prove that Pr[Cj is satisfied]34zj \mathrm{Pr}\left[C_j\ \text{is satisfied}\right] \ge \frac{3}{4} z^*_j .

Let’s look at the probability that each algorithm satisfies a clause of kk variables:

Now the proof boils down to the following table:

11 1212zj\frac{1}{2} \ge \frac{1}{2} z_j^* 1zj1 \cdot z_j^* 1212+12zj34zj\frac{1}{2} \frac{1}{2} + \frac{1}{2} z_j^* \ge \frac{3}{4} z_j^*
22 34zj\ge \frac{3}{4} z_j^* 34zj\frac{3}{4} \cdot z_j^* 34zj\ge \frac{3}{4} z_j^*
3\ge3 78zj\ge \frac{7}{8} z_j^* (11e)zj\ge\left(1 - \frac{1}{e}\right) \cdot z_j^* >34zj> \frac{3}{4} z_j^*


Algorithm (BIASED-SAT):

  1. vybereme nezávisle náhodně všechny literály
    • true: p>12p > \frac{1}{2}, jinak false; hodnotu pp najdeme později

Theorem: BIASED-SAT je (ϕ=512)\left(\phi = \frac{\sqrt{5} - 1}{2}\right)-aproximační algoritmus.

Uvažme CjC_j (a opět indikátorové veličiny YjY_j):

Po vyřešení p=1p2p = 1 - p^2 dostáváme p=ϕ=512p = \phi = \frac{\sqrt{5} - 1}{2}.

Nechť UU množina klauzulí bez záporných jednotkových.

(👀): OPTjUwj\mathrm{OPT} \le \sum_{j \in U} w_j

E[j=1mwjYj]=j=1mwjE[Yj]jUwjPr[Cj je splneˇnaˊ]jUwjppOPT \begin{aligned} \mathbb{E}\left[\sum_{j = 1}^{m} w_j Y_j\right] &= \sum_{j = 1}^{m} w_j \mathbb{E}\left[Y_j\right] \\ &\ge \sum_{j \in U} w_j \cdot \mathrm{Pr}\left[C_j\ \text{je splněná}\right] \\ &\ge \sum_{j \in U} w_j \cdot p \\ &\ge p \cdot \mathrm{OPT} \end{aligned}