### purplesyringa's blog

By purplesyringa, history, 4 weeks ago,

Does anyone know any way to solve this problem? My Google-Fu let me down.

$x_1, \dots, x_n$ are formal elements of an additive group. $S_1, \dots, S_m$ are subsets of $\lbrace 1, \dots, n \rbrace$. For a fixed family $S_1, \dots, S_m$, I want to devise an algorithm that computes each $s_i = \sum_{j \in S_i} x_j$, performing as few additions as possible in total.

For example, for $S_1 = \lbrace 1, 2, 3 \rbrace, S_2 = \lbrace 1, 3, 4 \rbrace$, the optimal algorithm is: $t = x_1 + x_3; s_1 = t + x_2; s_2 = t + x_4$. It performs 3 additions in total, as opposed to the simpler algorithm: $s_1 = x_1 + x_2 + x_3; s_2 = x_1 + x_3 + x_4$.

Heuristics like this one come to mind: find a pair of indices $i \ne j$ such that as many subsets as possible contain both $i$ and $j$, add $t = x_i + x_j$ to the algorithm and replace $x_i + x_j$ (up to commutativity/associativity) with $t$ in all subsets. Repeat until all subsets are singletons.

But other than that, I'm totally stuck here. I don't have any theoretical bounds, I don't know what an exhaustive solution looks like (other than iterating among all possible algorithms, that is), and I don't know what papers cover anything like this. Does anyone have any idea on any of this?

• +28