0
$\begingroup$

I have m bins (sums) and n summands. Each summand goes into a bin. In order to minimize the standard deviation, I have a greedy algorithm that appears to accomplish this. I am not sure of the name, but would like to know more. All m bins must have a sum greater than zero at the end of the algorithm.

It seems simple:

sort the summands from highest to lowest.

for each summand in the summands: find the first available bin with minimum sum and place it in the bin

I haven't proved anything about it, but I've come up with a few test data sets and it appears to work.

EDIT --- Here is my attempt at an analysis:

The algorithm seeks to minimize the standard deviation of m sums summed from n summands.

The mean is always the sum of n summands divided by m, that is given.

To minimize the standard deviation, the algorithm makes the greedy choice to minimize the standard deviation, or variance (either). I want to prove that the greedy choice is always the optimal choice.

Suppose there is a bin m1, not the minimum sum bin, that is a better choice than minimum sum bin m. Adding to this bin will minimize the standard deviation around u.

In other words, placing the next value n into this m will maximally decrease the variance, meaning that we have maximally decreased the sum of (m_i - u)^2. NOTE: m1' = m1 + x, m' = m + x, where x is the next summand.

So: remaining_sum_var + (m1' - u)^2 + (m - u)^2 < remaining_sum_var + (m' - u)^2 + (m1 - u^2) where m1 is greater than m.

Simplify and factor:

(m1' - u)^2 + (m - u)^2 < (m' - u)^2 + (m1 - u^2)

m1'^2 - 2um1' + 2u^2 + m^2 - 2um < m'^2 - 2um' + 2u^2 + m1^2 - 2um1

m1'^2 - 2um1' + m^2 - 2um < m'^2 - 2um' + m1^2 - 2um1

Ignoring linear terms whose difference will be constant (linearity).

m1'^2 + m^2 < m'^2 + m1^2

If we have added summand x to m1 this expands to:

(m1 + x)^2 + m^2 < (m + x)^2 + m1^2

m1^2 + 2m1x + x^2 + m^2 < m^2 + 2mx + x^2 + m1^2

2m1x < 2mx

m1 < m, this is a contradiction. So it cannot be the case that there is a better choice than minimum sum bin m.

$\endgroup$
7
  • $\begingroup$ What exactly is your question? Do you want to know whether your algorithm is correct? What do you mean by "minimize the standard deviation"? The standard deviation of what? We have resources on how to check whether your greedy algorithm is correct: cs.stackexchange.com/q/59964/755. Please try applying the ideas there, and edit your question to show what progress you've made and where you get stuck. $\endgroup$ – D.W. Sep 14 '20 at 6:18
  • $\begingroup$ Your algorithm is a heuristic, and there is no reason to believe that it always produces the optimal solution. Perhaps it always gives a good approximation. In practice its performance might be very good on real-world instances. $\endgroup$ – Yuval Filmus Sep 14 '20 at 7:50
  • $\begingroup$ @D.W. Thank you! Yes I would like to know if my algorithm is correct. I am trying to minimize the standard deviation of the sums. But really the question is, does a better algorithm exist or is there a name for the method that I have applied. $\endgroup$ – Anthony O Sep 14 '20 at 15:35
  • $\begingroup$ @YuvalFilmus Why do you say that it is a heuristic? Because it is not proven to be optimal? Is there an exception that you thought of? $\endgroup$ – Anthony O Sep 14 '20 at 15:36
  • 1
    $\begingroup$ A heuristic is an algorithm which works well in practice, but we don't know how to analyze. $\endgroup$ – Yuval Filmus Sep 14 '20 at 15:39
1
$\begingroup$

No, your algorithm does not always produce the optimal solution. When $m=2$, this is (at least as hard as) the Partition problem, which is NP-hard. Wikipedia discusses the greedy algorithm and lists a counterexample which shows that your algorithm does not work.

$\endgroup$
5
  • $\begingroup$ thanks! I suppose I can try another approach then. What do you recommend as the most practical to implement for the partition problem where there are more than 2 subsets? $\endgroup$ – Anthony O Sep 14 '20 at 17:37
  • $\begingroup$ I'm asking because its not quite the knapsack problem and its not quite the subset sum problem is it? The partition problem is only for subsets of size 2. $\endgroup$ – Anthony O Sep 14 '20 at 17:45
  • $\begingroup$ I've also looked at the bin packing problem. Surely this is a common algorithm for resource management. I am hoping to pin it down :) $\endgroup$ – Anthony O Sep 14 '20 at 17:59
  • $\begingroup$ @11010001101001, Trying to find a polynomial-time algorithm for a problem that is NP-hard is a recipe for disappointment. If you want to solve the problem in practice, I suggest asking a separate question about how to do that, and give parameter settings (typical values for sizes of each of the parameters). $\endgroup$ – D.W. Sep 15 '20 at 18:54
  • $\begingroup$ Thanks I did some more research into it and went with the MULTIFIT algorithm. The algorithm I implemented is the LPT algorithm I discovered. See my answer too the question. $\endgroup$ – Anthony O Sep 15 '20 at 20:37
0
$\begingroup$

I have discovered that the algorithm is the LPT Algorithm. It is covered here along with other algorithms for an example task: scheduling on parallel machines with fixed jobs. The problem is NP hard and NP complete. The polynomial time algorithms are approximations.

https://depositonce.tu-berlin.de/bitstream/11303/11089/3/grigoriu_liliana_2019.pdf

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.