# Reducing resource allocation problem to bipartite matching

There are a set of bins, $B$ and a set of resources $R$. Each $b \in B$ is associated with a set function $Z_b(S) : 2^R \rightarrow \mathbb{R}^+$. The resource allocation problem is to find a partition of $R$, $\{R_b : b\in B\}$ that maximizes $\sum_{b \in B} Z_b(R_b)$. This problem is NP-hard if no constraints are imposed on $Z_b$. Is there any way to reduce this to finding the maximum-weight matching over some bipartite graph? Of course the number of left/right nodes would have to be exponential in number since bipartite matching is solvable in poly-time.

## 1 Answer

Yes, there certainly is. There is a trivial solution. First, solve the resource allocation problem (which can be done in exponential time by enumerating all candidate solutions). Then, use the solution to construct a bipartite graph whose maximum-weight matching corresponds to the solution in some way; this is straightforward. Finally, output that graph. This takes exponential time, but any procedure to output a graph with exponentially many vertices can't avoid taking exponential time anyway. This meets all of your stated requirements.