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,…,m−1}U={0,1,…,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}}{{0},{1},{0,1},{0,1,2}}. It's upward closed: If XX is in the family then so are all Y⊃XY⊃X. Its minimal sets, one of which we want to find, are {0}{0} and {1}{1}. We can ask only questions of the form ‘is set XX 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 A⊆℘(U)A⊆℘(U). We maintain a current candidate XX. The invariant is that X∈AX∈A; the variant is that |X||X| decreases. We establish the invariant by setting X=UX=U. We decrease the size as follows: for each element, we throw it away if possible. More precisely, we iterate the elements uu of UU. If X−{u}X−{u} is still in AA, then we remove uu from XX.
Clearly, this algorithm asks exactly mm questions. Also, this solution finds the last set from AA, lexicographically. (The last set from AA is also minimal.)
Lower bound. Is mm questions the best we can do? In the worst case, yes. Here is why. Consider the families of sets with exactly one minimal set: AX={Y∣X⊆Y⊆U}AX={Y∣X⊆Y⊆U} There are 2m2m such families. To identify one of them, we need mm 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,…,m−10,1,…,m−1 and says
drop 00, | drop 11, | …… | drop u0−1u0−1, | keep u0u0, |
drop u0+1u0+1, | drop u0+2u0+2, | …… | drop u1−1u1−1, | keep u1u1, |
⋮⋮ | ⋮⋮ | ⋮⋮ | ⋮⋮ | ⋮⋮ |
drop uk−2+1uk−2+1, | drop uk−2+2uk−2+2, | …… | drop uk−1−1uk−1−1, | keep uk−1uk−1 |
drop uk−1+1uk−1+1, | drop uk−1+2uk−1+2, | …… | drop m−1m−1 |
and then returns the solution {u0,u1,…,uk−1}{u0,u1,…,uk−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 u0u0. To do so, we find the biggest vv such that {v,v+1,…,m−1}∈A{v,v+1,…,m−1}∈A. Why? First: If {u0,u1,…,uk−1}∈A{u0,u1,…,uk−1}∈A, then {u0,u0+1,…,m−1}∈A{u0,u0+1,…,m−1}∈A. Second: If {v,v+1,…,m−1}∈A{v,v+1,…,m−1}∈A, then v≤u0v≤u0; otherwise, {u0,u1,…,uk−1}{u0,u1,…,uk−1} wouldn't be the last element of AA.
In general, we found some prefix u0,u1,…,ui−1u0,u1,…,ui−1 and we search for uiui. Now we look at sets of the form {u0,u1,…,ui−1}∪{v,v+1,…,m−1}{u0,u1,…,ui−1}∪{v,v+1,…,m−1} and identify the biggest vv for which the set is in AA.
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:N→{0,1}f:N→{0,1} such that f(i)≤f(i+1)f(i)≤f(i+1) for all ii. We want to find the smallest ii such that f(i)=1f(i)=1. In the first phase we find some ii such that f(i)=1f(i)=1. We do so by evaluating f(1)f(1), f(2)f(2), f(4)f(4), f(8)f(8), f(16)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 ii, then the runtime is ∼lgi∼lgi.
The time needed to find uiui is roughly 1+lg(ui−ui−1)1+lg(ui−ui−1). The total runtime is 1+k+lgu0+lg(u1−u0)+⋯+lg(uk−1−uk−2)+lg(m−uk−1)1+k+lgu0+lg(u1−u0)+⋯+lg(uk−1−uk−2)+lg(m−uk−1). Let us denote the arguments of the logarithms by x0,…,xkx0,…,xk. With this notation, the worst runtime is maximum of1+k+lg(x0x1⋯xk)given thatx0+x1+⋯+xk=m The maximum is achieved when x0=⋯=xk=m/(k+1). (This can be shown by using Lagrange multipliers.) Thus, the maximum runtime is ∼k+klg(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.