6
$\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
  • 1
    $\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
2
$\begingroup$

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

There are decent approximation algorithms, though:

  • Greedy provides a $\tfrac{4}{3} - \tfrac{1}{3k}$-approximation (a PTAS).

  • FPTAS exist.

$\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.