2
$\begingroup$

Given positive numbers $x_1,x_2,\ldots,x_n$, a positive integer $k$, and a positive real number $D$, determine whether we can divide the numbers (according to the ordering) into $k$ parts so that each part has sum at least $D$.

A simple greedy algorithm works here: Find the least $i_1$ such that $x_1+x_2+\ldots+x_{i_1}\geq D$, then the least $i_2$ such that $x_{i_1+1}+x_{i_1+2}+\dots+x_{i_2}\geq D$, and so on. If we can get at least $k$ parts, the answer is yes. Otherwise the answer is no.

Assuming that we're allowed to query the sum of any subset of the $x_i$'s, this algorithm takes $O(k\log n)$ queries. Is there an algorithm that takes fewer queries?

$\endgroup$
  • $\begingroup$ In the comparison model, any algorithm which also outputs the partition must make at least $\Omega(k\log n)$ queries, since there are $\Theta(n^{k-1})$ potential answers. In many cases it is possible to show that the algorithm must "know" the answer, even if it only outputs Yes or No. $\endgroup$ – Yuval Filmus Dec 7 '17 at 14:48
  • $\begingroup$ It's easy to see the partial sums are the only useful input and that if you're only using comparisons and branching you can't do better than $\mathcal{O}(\log \binom{n}{k})$, which I think is $\mathcal{O}(k \log \frac{n}{k})$. $\endgroup$ – Veedrac Dec 7 '17 at 14:51
  • $\begingroup$ @YuvalFilmus Sorry, I've edited to specify the computation model. $\endgroup$ – user57012 Dec 7 '17 at 23:57
  • $\begingroup$ @YuvalFilmus, I don't see how you get a $\Omega(k \log n)$ bound on the number of queries. Each query might give more than one bit of information, since the query returns an integer (a sum). Perhaps you mean that $\Omega(k \log n)$ comparisons are needed? But maybe it's possible that there is an algorithm that queries $o(k \log n)$ sums, and does $\Omega(k \log n)$ comparisons of the results, so it's not clear to me how we get to an answer to the updated question. $\endgroup$ – D.W. Dec 8 '17 at 0:42
  • $\begingroup$ @D.W. That's right, I considered the comparison model. $\endgroup$ – Yuval Filmus Dec 8 '17 at 7:25

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.