# putting objects in buckets — optimization problem

Let $\mathcal B$ and $\mathcal O$ denote finite sets ("buckets" and "objects", respectively) and let $$E: \mathcal O \times \mathcal B \to \mathbb{R}_{>= 0}$$ be a function. Is there an algorithm that, given a partition of $| \mathcal B |$, $$| \mathcal B | = \sum_{b \in \mathcal{B}} \mu_b$$ returns a function $\varphi: \mathcal O \to \mathcal B$ maximizing the quantity $\sum_{o \in \mathcal O} E(o, \varphi(o))$, subject to the constraint that $| \varphi^{-1} (b)| = \mu_b$ for all $b \in \mathcal B$?

Motivation: all objects need to be put into a bucket, but the buckets have different sizes. The function $E$ gives the value of placing a given object in a given bucket. If the buckets each have a certain capacity, how can an optimal distribution of objects in buckets be found?

• How is E presented ? A lot depends on that. For special cases of E, one could design optimal algorithms via dynamic programming, but for other cases it would be NP-hard – Suresh Venkat Jul 2 '12 at 19:40

I assume that $\cal O$ and $\cal B$ are of polynomial size. One way to solve this problem is to reduce it to the Maximum Cost Bipartite Matching Problem. Consider the following bipartite graph $G = (L\cup R, E)$:
1. $L = \{b_i: b\in {\cal B}, 1\leq i \leq\mu_b\}$, that is, for every bucket $b$ and $i\in \{1,\dots, \mu_b\}$, we introduce a vertex $b_i$
2. $R = \cal O$
3. $E = L \times R$, the cost of the edge $(b_i,o)$ equals $E(o,b)$.
We find a maximum cost matching $M$ in $G$. Now we construct the solution to our original problem: bucket $b$ contains those objects that are matched in $M$ with vertices $b_1, \dots, b_{\mu_b}$. Clearly, each bucket $b$ contains $\mu_b$ objects. The value of this solution equals the cost of $M$.