1
$\begingroup$

There are $P$ buckets each with $n_p (p \in 1..P)$ items. Let $a$ be the average number of items, so $a = \frac{\sum_{p=1}^P n_p}{P}$.

Now for each pair of buckets $i$ and $j$, we need to transfer $t_{ij}$ items from $i$ to $j$ OR from $j$ to $i$. All $t_{ij}$ are known, but the direction of transfer is unknown. So I'm thinking of $t_{ij}$ as the absolute number being exchanged ($t_{ij} >= 0$). For any $i$, $\sum_{k=1}^P t_{ik} <= n_i$ and $t_{ii} = 0$ hold.

The goal is that after all transfers are done, the buckets should be balanced. This might be minimization of $\sum_{p=1}^P |n'_p - a|$ or something like that.

The algorithm need not actually minimize this, but somewhere close is good enough.

How can this be done?

$\endgroup$
2
  • $\begingroup$ I don't know how it can be done. For seriously unbalanced cases, you might try a greedy approach: find vertices i and j such that t_ij is maximal. If there are several, find those forming a cycle. Choose direction(s) to minimize the imbalance, do the transfer, and set the tij to zero. Except for cycle finding, this can be done pretty quickly. $\endgroup$ Jun 29, 2013 at 1:17
  • $\begingroup$ Could you give some context of your research? Moreover, what’s a brute force algorithm for solving your problem? If I understand you correctly, with known directions we would perform a brute-force search over all permutation of pairs. E.g. with 4 buckets, there’re 6 pairs, so we’d have to search over 720 permutations. With unknown directions, that number has to multiplied by $2^{6}$. Is the above a correct brute force approach to your problem? $\endgroup$
    – Waldemar
    Jul 1, 2013 at 11:10

0

Your Answer

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

Browse other questions tagged or ask your own question.