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$
$\endgroup$
3
-
$\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, 2016 at 5:58
-
$\begingroup$ You can approximate it by sampling permutations $\pi$. In many cases this is good enough. $\endgroup$– Yuval FilmusAug 14, 2016 at 6:56
-
$\begingroup$ I tried the reduction but i suspect it is tractable. $\endgroup$– Cole ComfortAug 14, 2016 at 7:33
Add a comment
|