3
$\begingroup$

Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example,

  • person 1 has item A, C, D, and wants item F
  • person 2 has item B, C, and wants E

  • person 3 has item E, and wants G

    ...

You get the idea. So it's basically a supply/demand matching problem, and if we represent this as a person-item matrix, it's gonna be a very sparse one.

So my question would be:

  1. How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?
  2. How do I find the shortest series (or path) that involves more than 2 people (so one-to-one exchange I think I've figured how by using some matrix operations)?
  3. What would be the complexity for finding longest/shortest paths?

Any advice would be appreciated.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ If you don't require the trades to form a single loop, then it sounds like you're looking for "math trades", look at Chris Okasaki's interesting write-up here and here (more algorithmic detail). Poly-time solvable and already implemented! :) OTOH if you do require a single loop, I can tell you right now that the problem is basically a generalisation of Hamiltonian Cycle and thus NP-complete. $\endgroup$ – j_random_hacker Oct 21 '16 at 16:09
  • $\begingroup$ all exchanges are one item for one item ? $\endgroup$ – njzk2 Oct 21 '16 at 18:45
  • $\begingroup$ Please do not post the same question on multiple Stack Exchange sites. You also posted this question on Software Engineering.SE (formerly Programmers.SE): softwareengineering.stackexchange.com/questions/334277/… $\endgroup$ – wythagoras Oct 21 '16 at 20:25
5
$\begingroup$

I'm assuming that items are always traded 1-for-1.

How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?"

If you are only looking for one long path, then you are looking for a Hamiltonian circuit if one exists, so the decision version of the problem is NP-complete. If you are open to having multiple disjoint cycles of exchange and just looking for as many items as possible involved in the exchange, then it is the MAX SIZE EXCHANGE problem from the Kidney Exchange literature, and it is solvable in polynomial time.

P. Biro, D. F. Manlove, and R. Rizzi. Maximum weight cycle packing in directed graphs, with application to kidney exchange programs. Discrete Mathematics, Algorithms and Applications, 1(04):499–517, 2009.

|cite|improve this answer
$\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.