TR-100: Sums of Lexicographically Ordered Sets

Abstract

We consider the problem of determining finite integer sets which are knapsack-solvable in linear time (i.e., it is possible to determine in linear time, for any integer b, whether b can be expressed as a sum of distinct elements of that set) and where the largest element is as small as possible. We study the condition that the k-subsets (for fixed k) when lexicographically ordered have increasing sums. We give an optimal construction of sets with this property, prove that it is unique, and give the asymptotic behaviour of the largest member. Using these results, we construct sequences of positive integers where the largest element is minimal, the subset sums are distinct and lexicographically ordered, and are knapsack-solvable in linear time.