Posts

Showing posts from April, 2021

Open Problem: Efficiently Evaluating Subset Sums

Suppose we are given a vector of $n$ items $ \begin{bmatrix} x_1 & x_2 & \dots x_n \end{bmatrix}$ and we would like to perform a number of subset sums on these items.  Specifically, we would like to compute $ \sum_{i \in S} x_i $ for some collection of subsets $S \subseteq \{ 1, \dots, n \}$.   We would like to evaluate all of the summations using the minimum number of arithmetic operations (additions and subtractions). In this setting, addition and subtraction of two elements is an expensive operation (e.g., think of them as being 2D numpy arrays).  Therefore, we are willing to spend computational time and resources to find an efficient means to evaluate the subset sums.  Moreover, we may need to compute these subset sums many times, e.g., if they are computed as part of an inner loop to an iterative algorithm.  Therefore, the time spent finding the right way to evaluate the subsets sums will ultimately pay for itself. A few examples with solutions to make this problem more co