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?
No idea how to prove that it's optimal but. Assume that the collection $$$M$$$ of subsets includes all nonempty intersections. Then we can compute sums of minimal elements first, and then when there are multiple supersets $$$S_1, ..., S_k$$$ of a set $$$S$$$ with sum $$$s$$$ we have:
So the total count of operations for $$$S, S_1, ..., S_k$$$ is
tldr: Just imagine the poset generated by the given sets and their intersections and compute the sums in topsort order.