I'm going to be given a positive integer $z$, and I want to find an optimal basis $B$ that is good for $z$.

A basis $B$ is a multiset of positive integers. The basis $B$ is considered good for $z$ if, for all non-negative integers $x,y$ such that $x+y=z$, we have the following: there exist multisets $B_x,B_y$ such that $x=\sum_{i \in B_x} i$, $y=\sum_{j \in B_y} j$, and $B_x \cup B_y \subseteq B$ (counting multiplicities: since these are multisets, the union operation adds up multiplicities of common elements, and the subset operation checks that multiplicities are pointwise smaller). In other words, for every possible way of decomposing $z$ into a sum of two non-negative integers, each of those integers has to be expressible as a sum of elements from the basis, and there have to be enough basis elements in $B$ that you don't "run out" of elements. When you use a basis element from $B$ to help express $x$, then it gets used up and you can't use that basis element for expressing $y$ (but if there's another copy in $B$, you're free to use the second copy for $y$). I hope this makes sense.

The size of a basis $B$ is the number of elements in the multiset $B$ (counting multiplicities). Smaller is better. An optimal basis is one that is as small as possible.

My question: is there a feasible algorithm that, given $z$, computes an optimal basis $B$ that's good for $z$? Or, an approximation algorithm that computes a basis that's reasonably close to optimal? How small can we make the basis, on average?

A naive algorithm: one simple approach is to use the basis $B=\{1,1,2,2,4,4,8,8,\dots,2^k,2^k\}$ (for $k=\lfloor \lg z \rfloor$), so the basis contains two copies of each power of 2 smaller than $z$. This is certainly good for $z$: we can express $x$ in binary, express $y$ in binary, and since we have two copies of each power of two, we won't run out of basis elements (even if some power of two is common to both binary expressions, that's OK, since we have two copies, one for $x$ and one for $y$). Its size is approximately $2 \lg z$, so it is pretty small. However, it is not optimal in general: this basis could be up to a factor of two larger than optimal, depending upon $z$. Can you do better?

If it helps, in my application I would expect $z$ to be no larger than 1000 or so.

  • $\begingroup$ I am sure you already computed an optimal basis for small values of $z$. It would help to give a few significant examples, in particular examples supporting your statement that this basis could be up to a factor of two larger than optimal. $\endgroup$ – J.-E. Pin Aug 27 '13 at 3:54
  • $\begingroup$ @J.-E.Pin, Here's an infinite family of examples. If $z=2^k-1$, then the basis $B=\{1,2,4,8,\dots,2^{k-1}\}$ works and is a factor of two smaller than the naive approach listed in the question. $\endgroup$ – D.W. Aug 27 '13 at 7:34

Your Answer

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

Browse other questions tagged or ask your own question.