2
$\begingroup$

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?

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

This can be reduced to an instance of the minimum-cost flow problem.

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.

So your question boils down to asking whether there are parallel algorithms for min-cost flow. Searching the literature will turn up a bunch of algorithms for that. If you use Google Scholar, you can find a number of papers on that subject.

$\endgroup$
  • $\begingroup$ Your suggest led me to Auction Algorithms for Network Flows, much appreciated! $\endgroup$ – Prateek Sep 6 '16 at 22:38

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.