2
$\begingroup$

I'm trying to find the name of this problem, and with it a reasonable algorithmic solution.

Setup: There are $n$ items with weights $w_1,\dots,w_n$, and $m<n$ buckets with target weights $a_1,\dots,a_m$, satisfying $\sum_iw_i=\sum_ja_j=1$. The goal is to find an assignment $f:\{1,\dots,n\}\to\{1,\dots,m\}$ of the weights to the buckets such that $f$ is nondecreasing (the weights have to be in the same order as the buckets) and the sum of the weights in each bucket is "close" to the target for that bucket.

The sense of "closeness" is up to the implementation (whatever is easiest to model), but for concreteness let's suppose this is least-squares error; then we can define the error of a given assignment as $\varepsilon(f)=\sum_{i=1}^m(\sum_{j:f(j)=i}w_j-a_i)^2$, and the goal is to find the $f$ that minimizes $\varepsilon(f)$.

This problem seems similar to the knapsack problem, but there are some differences in the constraints and I don't know if this is also NP-complete. Does this problem have a name or reduce to a named problem?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The fact that $f$ is non-decreasing makes the problem much easier, solvable in polynomial time.

You have to find a way to split the weights so that weights $1,\ldots,x$ go to bucket $1$, weights $x+1,\ldots,y$ go to bucket $2$, weights $y+1\ldots,z$ go to bucket $3$, and so on.

If you define $D(i,j)$ to be the best way to assign weights $j,\ldots,m$ to buckets $i,\ldots,n$ you can apply dynamic programming.

Improve this answer
$\endgroup$
2
  • $\begingroup$ In order to apply dynamic programming, we need some sort of recursive relation on $D(i,j)$. Obviously the solution is $D(1,1)$ and $D(n,j)$ assigns everything to bucket $n$; and $D(i,m)$ can be found in $O(n)$ by testing the weight against each bucket. But what relation are you seeing between the best assignment in your limited domain and the best assignment in a bigger domain? $\endgroup$
    – Mario Carneiro
    May 27, 2015 at 0:06
  • $\begingroup$ @MarioCarneiro Perhaps I didn't understand the question, but I don't think my domain is limited at all. Since $f$ is nondecreasing, if I assign weight $x$ to bucket $y$ then I can't assign weight $x-1$ to bucket $y+1$, right? $\endgroup$
    – Tom van der Zanden
    May 27, 2015 at 6:53

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.