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

CC BY-SA 4.0
2018-07-09T16:58:55.737Z
2018-07-09T16:58:55.737Z
D.W.
<p>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.</p>

<combinatorics><bipartite-graphs>
Reducing resource allocation problem to bipartite matching
Television
# Reducing resource allocation problem to bipartite matching

(Asked by: username_0 on 2018-07-09)

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.

**Tags:** combinatorics, bipartite-graphs


---

## 1 answers

### Answer by username_1 on 2018-07-09. Score: 1

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.


---

