# Scheduling problem of average sums with condition

Take a multiset $S=\{s_1,\ldots,s_n\} \subset \mathbb{N}$ and some $k \in \mathbb{N}$. Take $T$ to be the set of all sequences of the form $s_{\pi(1)},\ldots,s_{\pi(i)}$, such that $\sum_{j=1}^{i-1} s_{\pi(j)} < k \leq \sum_{j=1}^{i} s_{\pi(j)}$ where $\pi$ is a permutation of the indices of $S$ and $i\leq n$ . Is there an efficient algorithm to compute the average of the sum of members of $T$? This is of interest to me because of its application to scheduling.

• Are the $s_i$ provided in binary or unary? Have you tried reducing from subset-sum or some similar problem? – D.W. Aug 14 '16 at 5:58
• You can approximate it by sampling permutations $\pi$. In many cases this is good enough. – Yuval Filmus Aug 14 '16 at 6:56
• I tried the reduction but i suspect it is tractable. – Cole Comfort Aug 14 '16 at 7:33