Loop invariants

More generally, to argue about the behavior of our loop, consider the following while loop:

$$\text{\textbf{while} } P \text{\textbf{ do }} T$$

where $P$ is a predicate whose validity depends on (a collection of) variables $X$ and $T$ be a set of program instructions. Applying instructions $T$ on variables $X$ would result in $T(X)$. Let $R$ be a predicate on $X$. We say that $R$ is a loop invariant if the following holds: $P(X) \& R(X) \implies R(T(X))$ That is, if the statement $R$ is satisfied before the program enters the loop and $R$ is loop-invariant, then $R$ must be satisfied after the program leaves the loop.

Exercise 7

Prove: If $R_1$ and $R_2$ are loop invariants for a while-loop, then $R_1 \& R_2$ is also a loop invariant for the same while-loop.

Let us look at a more complicated example where proving the behavior of the program is much less obvious. We are given a collection of squares $\mathcal{S}$ of arbitrary sizes in the plane. Our goal is to pick as many non-overlapping (a.k.a. independent) squares as possible. How well can we solve this problem?

Figure 3: A collection of squares and the choice made by the algorithm (grey).

This problem is among the NP-hard problems, so we should not expect to solve it exactly by an efficient algorithm. In these notes, you will see a very simple heuristic that is always guaranteed to give at least $1/4$-fraction of an optimal solution (i.e. if an optimal solution has $r$ rectangles, the heuristic reports at least $r/4$ rectangles). The idea is quite intuitive: We should be tempted to pick squares that have smaller areas, rather than the big ones. This motivates the following algorithm.

INDSQUARES($\mathcal{S}$)

1. Initialize solution $\mathcal{I} \leftarrow \emptyset$
2. while $\mathcal{S} \neq \emptyset$ do
   1. Let $X$ be the smallest square in $\mathcal{S}$
   2. $\mathcal{I} \leftarrow \mathcal{I} \cup \{X\}$
   3. Remove from $\mathcal{S}$ all its squares that overlap with $X$
3. return $\mathcal{I}$

Let $\mathcal{M}$ denotes the maximum-cardinality of a subset of non-overlapping squares. Our goal is to argue that $\mathcal{I}$ contains only non-overlapping squares and that $|\mathcal{I}| \geq |\mathcal{M}|/4$.

Theorem 2

The following are loop invariants:

• (R1) No squares in $\mathcal{S}$ overlap with $\mathcal{I}$.

• (R2) $\mathcal{I}$ is a set of non-overlapping squares

• (R3) $|\mathcal{I}| \geq |\mathcal{M} - \mathcal{S}|/4$

Proof:

The first is easy to prove: Each while-loop updates $\mathcal{S}$ and $\mathcal{I}$. Suppose that (R1) holds before the loop. Now, when $X$ is added into $\mathcal{I}$, all squares overlapping with $X$ are removed from $\mathcal{S}$. Therefore, (R1) continues to hold after this update. The second requires the first. Suppose that (R2) holds before the loop. Since $\mathcal{I}$ is non-overlapping before the loop, from (R1), we know that $X$ cannot overlap with anything in $\mathcal{I}$. Therefore, $\mathcal{I} \cup \{X\}$ is also non-overlapping. Finally, suppose that (R3) holds before the loop, so we have that $|\mathcal{I}| \geq |\mathcal{M}- \mathcal{S}|/4$ (before). We need to argue that $|\mathcal{I}|+1 \geq |\mathcal{M} - (\mathcal{S} - \mathcal{S}')|/4$ where $\mathcal{S}' \subseteq \mathcal{S}$ contains the squares of $\mathcal{S}$ that overlap with $X$. Notice that $\mathcal{M} - (\mathcal{S} - \mathcal{S}') = (\mathcal{M} -\mathcal{S}) \cup (\mathcal{M} \cap \mathcal{S}')$It suffices to argue that $|\mathcal{M} \cap \mathcal{S}'| \leq 4$. Consider each square $Q \in \mathcal{S}' \cap \mathcal{M}$. This square $Q$ must be at least as large as $X$ (since we choose $X$ to be smallest in $\mathcal{S}$). Moreover, $Q$ overlaps with $X$, so $Q$ must contain a corner of $X$¹. However, since $X$ has only four corners, there can be at most four non-overlapping squares that contain its corner. It follows that $|\mathcal{M} \cap \mathcal{S}'| \leq 4$.

At the end of the algorithm, we can use (R2) to say that $\mathcal{I}$ is non-overlapping and (R3) to say that $|\mathcal{I}| \geq |\mathcal{M} - \emptyset|/4 = |\mathcal{M}|/4$. Notice that (R1) is not needed to make this implication; it is stated for the sole purpose of arguing that (R2) is a loop invariant. Proving algorithmic properties rigorously often requires this trick.

Exercise 8

Consider a collection of closed intervals $I_1,\ldots, I_n \subseteq {\mathbb R}$ on the line where $I_j = [l_j, r_j]$. Our goal is to choose as many non-overlapping intervals as possible.

• Consider the heuristic $A$: Choose the smallest interval, remove all intervals that overlap with it, and repeat. Prove that this heuristic always returns a solution of size at least half of that of the optimal solution.

• Consider the heuristic $B$: Choose the interval with minimum $r_j$, remove all intervals that overlap with it, and repeat. Prove that heuristic $B$ always returns an optimal solution.

Footnotes

1. We assume that the squares in the $\mathcal{S}$ are parallel for ease of explanation. ↩