I am working on a branch-and-bound algorithm for number partitioning, similar to Complete greedy algorithm. The input is a list of positive integers and an integer $k$; the output is a partitioning of the integers into $k$ bins, such that the smallest bin sum is as large as possible.
For the "bound" part, I want a function that takes as input a partial partition (a partition of the first $m$ integers) and the sum of the remaining integers, and returns an upper bound on the smallest sum. If this bound is not larger than the best solution found so far, then the branch can be pruned.
For example, suppose $k=3$, we have a partial partition with sums: $70, 90, 100$, and the sum of all remaining inputs is 30. Then, the upper bound is $95$, since in the best case, even if the remaining inputs are perfectly divisible, we would put $25$ in the first bin and $5$ in the second bin, so the best partition would be $95,95,100$.
I am looking for a fast algorithm to compute this upper bound. My current algorithm is as follows. Suppose we have a partial partition with sums $b_1\leq \ldots \leq b_k$, and the sum of remaining inputs is $s$. Then:
- If $b_1+s\leq b_2$, return $b_1+s$ (- put all remaining inputs in bin 1).
- Else, if $(b_1+b_2+s)/2 \leq b_3$, return $(b_1+b_2+s)/2$ (- divide all remaining inputs between bins 1 and 2 in a balanced way).
- Else, if $(b_1+b_2+b_3+s)/3 \leq b_4$, return $(b_1+b_2+b_3+s)/3$ ...
- Else, return $(b_1+\cdots+b_k)/k$.
Since the upper bound is calculated many times throughout the algorithm, I want the calculation to be as fast as possible.
QUESTION: Is there a faster way to compute this upper bound? I am looking both for improvements in runtime complexity (e.g. runtime that is sublinear in $k$), and for improvements in the constants.