Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  The Masked Avenger Jun 29 '13 at 1:17
    
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? –  Waldemar Jul 1 '13 at 11:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.