MIT 6.1220 — Lecture 18

Randomized Algorithms

Definition (Sublinear). An algorithm is sublinear if it runs in less than $O(n)$ time—less time than it takes to even read the whole input! (Naturally, these are approximation algorithms.)

Definition (Classical Approximation). In classical (e.g. optimization) problems, an approximation algorithm should return an answer within a factor of $\alpha$ of the correct one.

Definition (Decision Approximation). In decision problems, an approximation algorithm should:

Always return Yes for Yes-instances.
Return No with probability $\geq \frac{3}{4}$ if the input is “far” from a Yes-instance.
Otherwise, return either Yes or No. (We don't care.)

Problem. (Diameter) Consider a metric $d: [n] \times [n] \to \mathbb{R}^{\geq 0}$ that satisfies the triangle inequality, presented in the form of a symmetric $n \times n$ matrix $D$ . Output the diameter of $[n]$ , or the maximum entry of $D$ .

Find an approximation algorithm that runs in $o(N)$ , where $N = n^2$ is the size of the input.

Solution. (Diameter) Pick some $i \in [n]$ , and just return $\max_{j \in [n]} d(i, j)$ . By the triangle inequality, we're off by at most a factor of $2$ , and this runs in $O(n) = o(N)$ time. $\blacksquare$

Problem. (Connectivity) The input is a graph $G$ with $n$ vertices, each of which has degree at most $d$ . Decide whether $G$ is connected, as an approximation algorithm.

Remark. Solving this problem exactly requires $O(nd)$ time. To distinguish the graphs $K_{n/2} \sqcup K_{n/2}$ and $K_{n/2, n/2}$ , one must check $\frac{n}{2} \times \frac{n}{2} = \Theta(n^2)$ edges, which is indeed $\Theta(nd)$ , as $d = \Theta(n)$ for these graphs.

Solution. (Connectivity) Say an instance is considered far if it is not $\underline{\epsilon\text{-close to connected}}$ .

Definition. A graph $G$ on $n$ vertices and max degree $d$ is $\underline{\epsilon\text{-close to connected}}$ if one can add fewer than $\epsilon nd$ edges to make $G$ connected.

Let $G$ be a graph that is not $\epsilon$ -close to connected. Then the following are true.

Claim 1. The graph $G$ must have greater than $\epsilon d n$ connected components.

Proof: Obviously. $\square$

Claim 2. At least half of the connected components must have less than $\frac{2}{\epsilon d}$ vertices.

Proof: By claim 1, we have a lot of connected components. But we only have $n$ vertices. $\square$

Claim 3. At least $\frac{1}{2} \epsilon d n$ vertices are in connected components with less than $\frac{2}{\epsilon d}$ vertices.

Proof: Combine claims 1 and 2. Every connected component has at least one vertex. $\square$

Our strategy is to run the following process $\frac{C}{\epsilon d}$ times.

Process. Pick a random vertex $v$ . Run BFS on $v$ until either $v$ is discovered to be in a connected component with less than $\frac{2}{\epsilon d}$ vertices, or $\frac{2}{\epsilon d}$ vertices have been visited.

If we “catch” a vertex $v$ as being part of a connected component with less than $\frac{2}{\epsilon d}$ vertices, we declare No.

If $G$ is not $\epsilon$ -close to connected, the probability we discover this is:

\mathrm{Pr}[\text{one of the vertices is ``caught''}] \geq 1 - \left( 1 - \dfrac{1}{2}\epsilon d \right)^{C/\epsilon d} > 1 - \dfrac{1}{e^{C/2}}.

And the runtime is $O\left(\frac{C}{\epsilon d} \cdot \frac{2}{\epsilon d} \cdot d\right) = O\left(\frac{1}{\epsilon^2 d}\right)$ , which is sublinear. $\blacksquare$

Problem. (Sorted) Decide if a list of distinct numbers is sorted.

Remark. The list $(1, 3, 5, \dots, 2n - 1, 2, 4, 6, \dots, 2n)$ is a useful counterexample.

The list $(2, 1, 4, 3, \dots, 2n, 2n - 1)$ is another useful counterexample. (There's only $n$ inversions!)

Solution. (Sorted) Say an instance is considered far if it is not $\underline{\epsilon\text{-close to sorted}}$ .

Definition. A list is $\underline{\epsilon\text{-close to sorted}}$ if one can delete at most $\epsilon n$ elements and get a sorted list.

Our strategy is to run the following process $\frac{C}{\epsilon}$ times.

Process. Pick an index $i \in [n]$ uniformly at random. Compute the value $V = x_i$ . Now binary search for $V$ as if the list were sorted and you didn't know where it was.

If any of these binary searches fails, we declare No. The runtime is $O\left (\frac{C}{\epsilon} \cdot \log n\right )$ , which is sublinear.

To argue correctness, say an index $i$ is good if the binary search for $x_i$ succeeds.

Claim. If $i < j$ and $i$ and $j$ are both good, then $x_i < x_j$ .

Proof: Consider the binary search paths for $x_i$ and $x_j$ .

At some point they diverge; at that point, everything to the left (including $x_i$ ) better be smaller, and everything to the right (including $x_j$ ) better be bigger. $\square$

The point is that if we remove all elements that are not good, then the remaining list is sorted. Thus, if a list is not $\epsilon$ -close to sorted, it must have at least $\epsilon n$ elements that are not good.

So our probability of success is at least $1 - \left(1 - \epsilon\right)^{C/\epsilon} \geq 1 - e^{-C}$ , yippee. $\blacksquare$