<p>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)$:</p>

<ol>
<li>$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$    </li>
<li>$R = \cal O$    </li>
<li>$E = L \times R$, the cost of the edge $(b_i,o)$ equals $E(o,b)$.</li>
</ol>

<p>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$.</p>

CC BY-SA 3.0
2012-07-02T20:30:28.920Z
2012-07-02T20:30:28.920Z
Yury
<p>Let $\mathcal B$ and $\mathcal O$ denote finite sets ("buckets" and "objects", respectively) and let 
$$ 
E: \mathcal O \times \mathcal B \to \mathbb{R}_{&gt;= 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$?</p>

<p>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?</p>

CC BY-SA 3.0
2012-07-02T19:40:57.530Z
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
<ds.algorithms><optimization>
putting objects in buckets -- optimization problem
popstack
# putting objects in buckets -- optimization problem

(Asked by: username_0 on 2012-07-02)

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?

**Tags:** ds.algorithms, optimization

> **Comments:**
> **username_1**: 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  

---

## 1 answers

### Answer by username_2 on 2012-07-02. Score: 6

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


---

