-1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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