HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Balanced Weight Distribution in Bins/Buckets

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
bucketsweightbalancedbinsdistribution

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#33493, answer score: 2

Revisions (0)

No revisions yet.