4
$\begingroup$

Let $W = \{w_1,w_2,...w_n\}$ be a set of integer weights. Let $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Let $T(b_j)$ represent the total weight present in bucket $b_j$, which is the sum of all the weights present in $b_j$.

What is the optimal way to distribute all the weights $w_i$ into the buckets $b_j$ to minimize the metric $\max T(b_j) - \min T(b_k)$ for some $j,k \leq n$?

I know that this seems to be a variant of the bin packing problem and I have found some heuristics such as the ones described here.

But is this problem really equivalent to the one in the link? My problem does not have an upper limit on the capacity of each bucket, which makes it quite different from the routine bin-packing problem.

If anyone has an optimal solution and if it's NP-hard, an approximation algorithm, I'd love to hear it.

$\endgroup$
  • $\begingroup$ It's NP-hard. When $m=2$, you can get a gap of zero iff the set $W$ can be partitioned into two equal halves. $\endgroup$ – Yuval Filmus Nov 25 '14 at 3:31
  • $\begingroup$ You are right, it's actually the $k$-partition problem. $\endgroup$ – laughing_man Nov 26 '14 at 3:38
  • $\begingroup$ I have a similar problem (m=2), where I want the partition sums to have a ratio, as close as possible to a target ratio (instead of having the minimum difference). Can I use the same algorithms? How would I modify them? $\endgroup$ – kavadias Feb 7 '17 at 15:34
1
$\begingroup$

It seems that this is exactly the $k$-partition problem described here, which is NP-hard even in the $k=3$ case.

Partition Problem

$\endgroup$
  • 2
    $\begingroup$ This doesn't answer the query for algorithms. $\endgroup$ – Raphael Nov 26 '14 at 10:48
  • $\begingroup$ The link provides two different approximation algorithms - the greedy algorithm and the difference algorithm: en.wikipedia.org/wiki/Partition_problem#The_greedy_algorithm and en.wikipedia.org/wiki/Partition_problem#Differencing_algorithm. Should I still add them in the answer? Sorry I am not sure whether to repeat information provided in the link since I'm new here. $\endgroup$ – laughing_man Nov 30 '14 at 6:17
  • $\begingroup$ Every answer should be able to stand on its own to some extent. References (to peer-reviewed articles, ideally) are fine (and necessary) but always try to think, what if my links break or the document I link to changes? $\endgroup$ – Raphael Dec 1 '14 at 10:00

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.