0
$\begingroup$

I have $n$ variables $b_1,\ldots,b_n$, each one $b_k\in \{0,1\}.$ Associated to each binary vector ${\bf b}=[b_1,\ldots,b_n]$ there are strictly positive function values $f({\bf b})$, and these are given beforehand. In total there are $2^n$ $f({\bf b})$-values. Now, define $v_n$ as $$v_k \triangleq \max_{{\bf b}:b_k=1}f({\bf b})-\max_{{\bf b}:b_k=0}f({\bf b}).$$

Problem statement: What is the smallest number of comparisons needed to evaluate all the $n$ values $v_1,\ldots,v_n$?

(With a comparison, I mean comparing the magnitude of some $f({\bf b})$ and $f(\tilde{\bf b})$.)

Improve this question
$\endgroup$
6
  • $\begingroup$ What is the context? $\endgroup$
    – Douglas Zare
    Apr 21, 2013 at 22:17
  • $\begingroup$ I asked for context because divide-and-conquer works so well that it makes the problem look like an exercise, which would make it off-topic. $\endgroup$
    – Douglas Zare
    Apr 22, 2013 at 9:03
  • $\begingroup$ With some knowledge about $f$, you could use bucket sort on (f(b),b) pairs and never compare two f values directly at all. $\endgroup$
    – Eric Tressler
    Apr 22, 2013 at 14:47
  • $\begingroup$ @Douglas: Can you expand please? $\endgroup$
    – Brendan McKay
    Apr 22, 2013 at 15:15
  • 1
    $\begingroup$ This problem comes up naturally in digital modulation theory in the computation of the log-likelihood-ratios (LLR), i.e., the posterior probability of each bit given the received signal. The $f(\cdot)$ values are the so called metrics. In fact, the problem is the max-log-map approximation. This being said, Douglas's solution is not optimal. For his solution we have $$\frac{g(n)}{2^n}\to 3, n\to\infty$$ but this is not the smallest constant. $\endgroup$
    – pierre robert
    Apr 23, 2013 at 16:47

2 Answers 2

Reset to default
1
$\begingroup$

Since other people are interested, I'll post my answer. However, I would like to see more context provided to see what types of bounds are desired (is $\Theta(g(n))$ enough?), and how this problem could come up other than being assigned as an exercise.

It takes $\Theta(2^n)$ comparisons.

The lower bound is trivial. Consider the graph where you connect two vertices of the cube with an edge if you have compared their values. Vertices in separate components can't be compared regardless of the results of the comparison.

It would be easy to get an upper bound of $O(n2^n)$ by sorting the values. However, $O(2^n)$ is possible by using divide-and-conquer. Break the cube up into the top half, $\lbrace (1,\star,\star,...) \rbrace$, and the bottom half, $\lbrace(0,\star,\star,...)\rbrace$. Find the maximums on each $(n-2)$-dimensional face of the top and bottom halves. Then each $(n-1)$-dimensional face of the whole cube is either one of these halves, or a union of a face from the top half and a face from the bottom half. In the former case, we can maximize over two opposite faces of that half with one comparison (e.g., on $\lbrace (1,\star, \star, ...) \rbrace$ compare the maximum on $\lbrace (1,0,\star,\star,...)\rbrace$ with the maximum on $\lbrace (1,1,\star,\star,...)\rbrace$). In the latter case, we compare the values from the top half and from the bottom half (e.g. on $\lbrace (\star,1,\star,...) \rbrace$ compare the maximum on $\lbrace (1,1,\star,\star,...)\rbrace$ with the maximum on $\lbrace(0,1,\star,\star,...)\rbrace$). So if $g(n)$ is the number of comparisons for the $n$-dimensional cube, $g(n) = 2g(n-1) + 2n$, so $g(n)$ is $O(2^n)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Does this work if f is not injective? Gerhard "Ask Me About System Design" Paseman, 2013.04.22 $\endgroup$
    – Gerhard Paseman
    Apr 22, 2013 at 23:34
  • $\begingroup$ @Gerhard Paseman: Yes, you can just remember the maximum values on the top-dimensional faces, or at least one location of the highest value. $\endgroup$
    – Douglas Zare
    Apr 22, 2013 at 23:47
0
$\begingroup$

As Eric Tressler mentioned in the comments, you could use bucket sort which essentially means (by somehow using knowledge of f()) for each b, place b in the list at hash index f(b), then starting at the max index and looping down, use the list to update the values needed. While this does not directly compare values of f, it does assume some external ordering to the set of values which is accessible to the loop, and for me seems like an implicit comparison. Further, there are f for which you will need to loop through all the values before getting enough info to fill in for all the v_n. Even if f satisfies your condition that it is injective, you may still need to go through half the values, which for bucket sort gets prohibitive even for n above 25.

If you don't know enough about f, you have to look at all of the values to find the largest one. Once you have the set of b for which f(b) is largest, say it has s-many such b, you have enough information to fill in about n + lg(s) instances of the max subexpressions for v_n, where I use lg to be log in base 2 rounded down to the nearest integer. While it may be possible to memoize and save on f(b) comparisons, a straightforward algorithm gives the result after at most (n+1)2^n comparisons, and minor modifications might get the (n+1) factor down to (1+lgn), but not without a lot of additional comparisons of values of b or parts of b. I recommend tracking the k largest useful values to start, for some small value of k < 2n, and iterating through the necessary b. You can repeat this as often as needed to resolve unknown values of v_n.

Like Douglas Zare, I would appreciate more context. I would like to know if this is homework-related before sharing any more on this problem.

Gerhard "Ask Me About System Design" Paseman, 2013.04.22

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.