0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Suresh Venkat Jul 2 '12 at 19:40
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.