3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.