*This post describes a very nice use of binary search.
I learned about it from a paper by Joao Marques-Silva, Mikolas Janota, and Anton Belov.*

Let's fix the universe to be $U=\{0,1,\ldots,m-1\}$. Whenever I say ‘set’ I mean ‘subset of the universe’.

**Problem.**
Many problems reduce to the following one:
*Given a non-empty upward-closed family of sets, find one of its minimal sets.*
As an example, take the family of sets $\{\{0\},\{1\},\{0,1\},\{0,1,2\}\}$.
It's upward closed: If $X$ is in the family then so are all $Y\supset X$.
Its minimal sets, one of which we want to find, are $\{0\}$ and $\{1\}$.
We can ask only questions of the form ‘is set $X$ in the given family?’

**A simple solution.**
I bumped into this problem while working on refinement for parametric analyses.
The solution I found was the following.
We are given ${\cal A}\subseteq \wp(U)$.
We maintain a current candidate $X$.
The invariant is that $X\in{\cal A}$; the variant is that $|X|$ decreases.
We establish the invariant by setting $X=U$.
We decrease the size as follows: for each element, we throw it away if possible.
More precisely, we iterate the elements $u$ of $U$.
If $X-\{u\}$ is still in $\cal A$, then we remove $u$ from $X$.

Clearly, this algorithm asks exactly $m$ questions.
Also, this solution finds the *last* set from $\cal A$, lexicographically.
(The last set from $\cal A$ is also minimal.)

**Lower bound.**
Is $m$ questions the best we can do?
In the worst case, yes.
Here is why.
Consider the families of sets with exactly one minimal set:
$$ {\cal A}_X = \{\,Y\mid X \subseteq Y \subseteq U\,\} $$
There are $2^m$ such families.
To identify one of them, we need $m$ bits of information.

At this point I stopped looking for a better solution.
I did so *despite* being told by Mikoláš Janota that better is possible.
My attitude was: Improvements to the average case are tricks, not algorithms.
I now think that that is a very bad attitude.

**A better solution.**
The previous solution goes through $0,1,\ldots,m-1$ and says

drop $0$, | drop $1$, | $\ldots$ | drop $u_0-1$, | keep $u_0$, |

drop $u_0+1$, | drop $u_0+2$, | $\ldots$ | drop $u_1-1$, | keep $u_1$, |

$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |

drop $u_{k-2}+1$, | drop $u_{k-2}+2$, | $\ldots$ | drop $u_{k-1}-1$, | keep $u_{k-1}$ |

drop $u_{k-1}+1$, | drop $u_{k-1}+2$, | $\ldots$ | drop $m-1$ |

and then returns the solution $\{u_0,u_1,\ldots,u_{k-1}\}$.

The long runs of drops are wasteful, if the output is small. The trick is to use binary search to find the next element to keep.

We start by finding $u_0$. To do so, we find the biggest $v$ such that $\{v,v+1,\ldots,m-1\}\in{\cal A}$. Why? First: If $\{u_0,u_1,\ldots,u_{k-1}\}\in{\cal A}$, then $\{u_0,u_0+1,\ldots,m-1\}\in{\cal A}$. Second: If $\{v,v+1,\ldots,m-1\}\in{\cal A}$, then $v\le u_0$; otherwise, $\{u_0,u_1,\ldots,u_{k-1}\}$ wouldn't be the last element of $\cal A$.

In general, we found some prefix $u_0,u_1,\ldots,u_{i-1}$ and we search for $u_i$. Now we look at sets of the form $$\{u_0,u_1,\ldots,u_{i-1}\}\cup\{v,v+1,\ldots,m-1\}$$ and identify the biggest $v$ for which the set is in $\cal A$.

The second trick is that we use open-ended binary search.
If you are familiar with it, then it's safe to skip this paragraph.
The simplest example of open-ended binary search is the following:
Consider a function $f:\mathbb{N}\to\{0,1\}$ such that $f(i)\le f(i+1)$ for all $i$.
We want to find the smallest $i$ such that $f(i)=1$.
In the first phase we find *some* $i$ such that $f(i)=1$.
We do so by evaluating $f(1)$, $f(2)$, $f(4)$, $f(8)$, $f(16)$, and so on.
After this first phase, we can use normal binary search.
We will need the following observation:
If the solution is $i$, then the runtime is $\sim \lg i$.

The time needed to find $u_i$ is roughly $1+\lg(u_i-u_{i-1})$. The total runtime is $1+k+\lg u_0 + \lg(u_1-u_0) + \cdots + \lg(u_{k-1}-u_{k-2})+\lg(m-u_{k-1})$. Let us denote the arguments of the logarithms by $x_0,\ldots,x_k$. With this notation, the worst runtime is $$\begin{align} &\text{maximum of}&&1+k+\lg(x_0x_1\cdots x_k) \\ &\text{given that}&&x_0+x_1+\cdots+x_k=m \end{align}$$ The maximum is achieved when $x_0=\cdots=x_k=m/(k+1)$. (This can be shown by using Lagrange multipliers.) Thus, the maximum runtime is $\sim k+k\lg(m/k)$. This runtime depends on two parameters: $m$ describes the input, and $k$ describes the output.

I think it is clear now that this is not ‘just a trick’, but a cute algorithm. I learned at least the following:

- If you can't improve the worst-case, try to improve something else.
- Average case analyses are sometimes difficult because you lack a distribution that describes the inputs realistically.
In that case, try to improve the runtime when seen as a function of both input size
*and*output size. - Listen more carefully to what Mikoláš says. :)

**References.**
If you want to find out more, look at the following articles:

- [Marques-Silva et al,
*Minimal Sets over Monotone Predicates in Boolean Formulae*, 2013]: This is the paper from which I learned the algorithm presented above. In it, you will also find another (older) algorithm with the same asymptotic performance. - [Marques-Silva, Janota,
*Computing Minimal Sets on Propositional Formulae I: Problems & Reductions*, 2014]: Read this if you didn't believe me that*many*other problems reduce to this one.

## No comments:

## Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.