# Parallel Algorithm for Donor/Recipient Matching - Graph Matching/Optimization

I'm not certain I can accurately describe the problem using my knowledge of discrete math, so pardon any inaccuracies. Happy to clarify any part of the question which is unclear.

Given the following constraints:

• Two sets, each with 'n' elements: 'donors' and 'recipients'. $|D| = |R| = n$
• Each donor has a maximal number of times they are able to be matched with a recipient: "max donations". $maxd: D \to \mathbb{Z}_{+}$
• A distance function, returning a real number representing the suitability of match between a donor and a recipient, given the number of times a donor has already "donated" / been matched with a recipient. $distance: D \times R \times \mathbb{Z}_{+} \to \mathbb{R}_{+}$

Devise a parallel algorithm to determine the list of optimal matching. i.e. find functions $m: D \to \mathcal{P}(R)$ which defines a partition of $R$ and $l: D \times R \to \mathbb{Z}_{+}$ such that $\forall d \in D$ $| m(d) | \leq maxd(d)$

which minimize the following cost:

$$\sum_{d \in D} \sum_{r \in m(d)} distance(d, r, l(d, r))$$

Intuitively, I think this is NP-hard. So I was satisfied with my solution - using BSP treat the donations per donor in phases, where each iteration is a graph matching problem.

Is this the best I can do? Any suggestions?

• I don't think this is NP-Hard. It seems like standard min-cost flow. However, I do not have a parallel algorithm atm. – Nicholas Mancuso May 15 '15 at 21:57

Build a flow network from your graph, with an edge from each donor to each recipient whose maximum flow is $1$ and whose cost is the negation of the value of that matching. Add a source vertex $s$, with an edge of weight $\text{maxd}(d)$ and cost $0$ to each donor $d \in D$. Add a sink vertex $t$ with an edge of cost $0$ and maximum weight $\infty$ from each recipient to $t$. Now compute the minimum-cost flow. This can be done in polynomial time, so your problem can be solved in polynomial time.