1
$\begingroup$

edited for clarity:

I have two functions–$f(x)$ which returns an integer and $T(x)$ which returns a boolean–that operate on a bit array of length $n$. I am trying to maximize $f(x)$ over all $x$ which satisfy the condition $T(x) = true$. I also know that if $b$ is a binary subset of $a$ then $f(a) > f(b)$ (e.g. $f(0b1101) > f(0b1001)$. I have no such insight about $T$. Can I avoid iterating over candidates which are subsets of inputs which satisfy $T$?

My current solution is this: beginning with $x = 1^n$ and an empty array as a cache, iterate through the various permutations in order of descending population count. Test if the next input $x$ is a subset of any values in the cache. If it is not a subset and $T(x)=true$, then compute $f(x)$ and add $x$ to the cache of supersets.

However, this strategy must search through the cache on every iteration. Instead, I am imagining a tree which (for $n=5$) looks like $$0b11111$$ $$0b11110\qquad0b11101\qquad0b11011\qquad0b10111\qquad0b01111$$ $$...$$ The root node is $1^n$, and child nodes are created by changing a single $1$ to a $0$ so that all children are binary subsets of their parents. Iterating from the root node, when we reach a node $x$ for which $T$ is true, we could skip calculating $f$ or $T$ for all of its child nodes because they are binary subsets of $x$. Unfortunately, the tree as constructed has $n!$ nodes instead of $2^n$, and nodes begin to appear multiple times in each sub-tree, so pruning the tree is not so simple. Is there a way to realize this type of optimization?

$\endgroup$
  • 1
    $\begingroup$ The maximum is $f(1^n)$. I suggest you rephrase your question to eliminate the function $f$. Explain what you want to accomplish only using the function $T$. $\endgroup$ – Yuval Filmus May 22 '15 at 5:59
  • $\begingroup$ The maximum is not $f(1)$ and I believe both functions are required to understand the problem. $T(x)$ must be true for $f(x)$ to be valid and $T$ and $f$ are not related in any way. Perhaps I can help with some more specifics? It does feel a little wordy. $\endgroup$ – Dylan MacKenzie May 22 '15 at 6:04
  • $\begingroup$ Bottomline – I cannot understand the problem you're trying to solve. Are you trying to maximize $f(x)$ over inputs such that $T(x)$? Moreover, you are assuming that $f$ is monotone. Do you have any assumptions on $T$? $\endgroup$ – Yuval Filmus May 22 '15 at 6:17
  • $\begingroup$ Correct, I am trying to maximize $f(x)$ over inputs for which $T(x)$ is true, and there are no assumptions for $T$. $\endgroup$ – Dylan MacKenzie May 22 '15 at 6:19
  • $\begingroup$ I edited the question to clarify my intent. Thank you. Also, I don't believe $f$ is strictly monotonic. $f(0b1000)$ is not necessarily greater than $f(0b0001)$ because $0b0001$ is not a binary subset of $0b1000$. $\endgroup$ – Dylan MacKenzie May 22 '15 at 6:29
2
$\begingroup$

There's no possibility of an efficient algorithm here, unless you have more information about $T$. $T$ might only return true for one input and, in the worst case, you'd have to try all $2^n$ possibilities for that input before finding the right one. Or $T$ could return true iff its input contains $n/2$ $1$'s: there are exponentially many such strings and you'd have to try all of them to maximize $f$, since none of those strings is a binary subset of any of the others, so you have no information about the behaviour of $f$ on that set of strings.

$\endgroup$
  • $\begingroup$ I realized that this would do nothing for the worst case performance, but I was hoping there were some easy gains to be had for random input. I have yet to benchmark the "cache" idea; it might actually slow things down. $\endgroup$ – Dylan MacKenzie May 22 '15 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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