Efficiently computing certain subset sums?

Правка en1, от purplesyringa, 2024-08-15 01:23:38

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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский purplesyringa 2024-08-15 01:23:38 1284 Initial revision (published)