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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.