I have a problem I am developing a solution for and currently I solve it with a brute force solution that checks all possibilities. It works for small numbers of bins but I'd like to work with a reasonable speed for increasing numbers, however the algorithm I use (brute force) increases in computing time in a factorial manner related to the number of bins. In other words it gets way too slow pretty quickly after about 6 or 7 bins. I'd like to classify the problem to see if it is NP-Complete, NP-Hard or other so I know where to look in attempting to optimize.
The basic problem is this.
You have a number of points n and you have weights for these points. The points also have an ordering such that points in a bin must be consecutive. You must place these into a total of a maximum of k bins. The bins contain an estimate for the set of points placed in it and the total error of the absolute value of difference in the points and the estimate must be minimized. The goal is to find how to place these points in the bins to have the minimal total error.
Thanks!
k-1
cuts to that sequence, such that the variance within the resulting segments is minimized, right? – tobias_k Jul 13 '13 at 13:03