Given an array $|A|=n$ of integers, and $m,k \in \mathbb{N}$, I want to find $m$ elements $a_{i_1},...,a_{i_m}$ of $A$ such that $\sum a_{ij} \geq k$ (repitions allowd), or determine that no such solution exists.

Clearly, a trivial solution is to take the maximal element $a_{max} = \max_{i} A_i$, multiply it by $m$, and if $ma_{max} \geq k$ return it.

Is there a polynomial time algorithm $X$ such that: $X$ is a randomized algorithm, and at every run, it outputs such $m$ elements where every $m$ elements have a positive probability to be generated by $X$? (for example, the above method does not satisfy it because on a given $A,m,k$ it will output one answer with probability 1, and many possible other solutions with probability 0). Is there an algorithm where every $m$ elements have an equal probability to be generated (i.e. the algorithm is uniform)?

  • $\begingroup$ Pick a random subset of size $m$, if the sum is $\ge k$ return it, else return $(a_{max}, a_{max}, \dots)$. This algorithm has a positive probability of every solution being returned. $\endgroup$ – Jakube Sep 20 '18 at 10:12
  • $\begingroup$ thanks! it will work. I edited and added uniform requirements, any ideas now? $\endgroup$ – SomeoneHAHA Sep 20 '18 at 11:05
  • $\begingroup$ Since SUBSET-SUM is NP-hard, I would expect the answer to be 'no'. $\endgroup$ – Yuval Filmus Sep 20 '18 at 16:56
  • $\begingroup$ Do you need an exactly uniform distribution on the set of all solutions; or only something that is approximately uniform? $\endgroup$ – D.W. Sep 20 '18 at 20:09
  • $\begingroup$ Both are ok, but in the case of approximation, does it mean that there is no exact solution? $\endgroup$ – SomeoneHAHA Sep 20 '18 at 20:50

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.