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

Improve this question
$\endgroup$
3
  • $\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
    Commented Nov 25, 2014 at 3:31
  • 1
    $\begingroup$ You are right, it's actually the $k$-partition problem. $\endgroup$
    – laughing_man
    Commented Nov 26, 2014 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
    Commented Feb 7, 2017 at 15:34

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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