# Is this subset-sum-type problem discussed in the literature?

Let $y \in \mathbb{Z}_+^n$, with $y_1 < \dots < y_n$. I am interested in finding a 0-1 matrix $A$ and $x \in \mathbb{Z}_+^m$ s.t. $m$ is minimal and $Ax = y$, where I am guaranteed that at least one such pair $(A,x)$ exists by requiring that $\sum_{j = 1}^m x_j = y_n$. I am "really" only interested in $x$.

For example, say I have $y = (3,5,7,10,12,26)^*$. Then $x = (3,5,7,11)^*$.

This strikes me as similar to a subset sum or number partitioning problem, but I can't find a reference for it and (after trying a bit nevertheless) don't really know how to look for one. Is this problem studied--or better yet efficiently solved--in the literature?

## 1 Answer

David Moulton looked at a related problem in Representing powers of numbers as subset sums of small sets, J Number Theory 89 (2001) 193-211, MR1845235 (2002j:11015), only he allowed negative entries in $x$. Mike Develin followed up in On optimal subset representations of integer sets, J. Number Theory 89 (2001) 212–221, MR1845235 (2002k:11032), and then Donald Mills wrote Some observations on subset sum representations, Integers 6 (2006) A25, MR2264840 (2007g:11027).