<p>You can fill sparse matrix vis match score between pairs . each row, column some person. And then you should select maximum on each row and maximum on each column if they are matched you should associate them.</p>

<p>It is not optimal algorithm. If you need optimal you should write dynamic program similar to one in Edit Distance. </p>

CC BY-SA 2.5
2011-02-05T13:46:17.537Z
This isn't a deterministic algorithm. What do you do if the maximum on some row isn't the maximum on the corresponding column?
Peter Shor 
CC BY-SA 2.5
2011-02-05T13:07:40.970Z
2011-02-05T13:14:57.987Z
2011-02-05T13:14:57.987Z
yura
<p>I'm writing an application which divides a population of users into pairs for the purpose of performing a task together. Each user can specify various preferences about their partner, e.g.</p>

<ul>
<li>gender</li>
<li>language</li>
<li>age</li>
<li>location (typically, within X miles/kilometers from where the user lives)</li>
</ul>

<p>Ideally, I would like the user to be able to specify whether each of these preferences is a "nice to have" or a "must have", e.g. "I would prefer to be matched with a native English speaker, but I must not be matched with a female".</p>

<p>My objective is to maximise the overall average quality of the matches. For example, assume there are 4 users in the system, A, B, C, D. These users can be matched in 3 ways:</p>

<pre>
Option 1     Match Score
A-B           5
C-D           4
---
Average       4.5

Option 2     Match Score
A-C           2
B-D           3
---
Average       2.5

Option 3     Match Score
A-D           1
B-C           9
---
Average       5
</pre>

<p>So in this contrived example, the 3rd option would be chosen because it has the highest overall match quality, even though A and D are not very well matched at all.</p>

<p>Is there an algorithm that can help me to: </p>

<ul>
<li>calculate the "match scores" shown above</li>
<li>choose the pairings that will maximise the average match score (while respecting each user's absolute constraints)</li>
</ul>

<p>It is not absolutely necessary that each user is matched, so given a choice between significantly lowering the overall quality of the matches, and leaving a few users without a match, I would choose the latter.</p>

<p>Obviously, I would like the algorithm that calculates the matches to complete as quickly as possible, because the number of users in the system could be quite large.</p>

<p>Finally, this system of computing match scores and maximizing the overall average is just a heurisitic I've come up with myself. If there's a much better way to calculate the pairings, please let me know.</p>

<h2>Update</h2>

<p>The problem I've described seems to be a similar to the <a href="http://en.wikipedia.org/wiki/Stable_marriage_problem" rel="nofollow">stable marriage problem</a> for which there is a well-known solution. However, in this  problem I do not require the chosen pairs to be stable. My goal is to choose the pairs so that the average "match score" is maximized</p>

CC BY-SA 2.5
2011-01-31T16:21:51.553Z
Welcome to CSTheory, @Don!
Daniel Apon
CC BY-SA 2.5
2011-01-31T16:42:08.163Z
http://en.wikipedia.org/wiki/Hungarian_algorithm ?
Peter Taylor
CC BY-SA 2.5
2011-01-31T18:40:54.280Z
Hungarian algorithm can be applied to bipartite graphs. I think Edmond's matching algorithm would be more convinient for this problem. for an implementation: http://www.xs4all.nl/~rjoris/maximummatching.html
Arman
CC BY-SA 2.5
2011-02-01T04:37:44.823Z
If the objective function to maximize is the _sum_ of the score of each match, the problem is called “maximum weighted matching in general graphs” ([Wikipedia](http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm#Weighted_matching)).  If you really want to maximize the _average_ score of a match, then it is always the optimal to choose only one match (with the maximum score).  The problem is underspecified if you want something in between.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-01T06:11:44.457Z
Tsuyoshi, it sounds like he wants a perfect matching (although it's not clear such a matching exists), in which case the sum and average are minimized the same way
Suresh Venkat
CC BY-SA 2.5
2011-02-01T16:49:17.883Z
@Suresh: My comment is based on the following part of the question: “It is not absolutely necessary that each user is matched, so given a choice between significantly lowering the overall quality of the matches, and leaving a few users without a match, I would choose the latter.”
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-01T16:57:48.123Z
@Tsuyoshi ah fair enough. that *does* leave it ill specified.
Suresh Venkat
CC BY-SA 2.5
2011-02-01T17:48:55.453Z
One option is to consider maximum weight matching among all matchings of a given cardinality k which should be also doable in polynomial time. Once you guess k the question of sum and average goes away and it may also be helpful to consider different values of k.
Chandra Chekuri
CC BY-SA 2.5
2011-02-01T21:58:32.370Z
@Chandra: How do we find all matchings of a given cardinality k in polynomial time? Do you have any reference?
Arman
CC BY-SA 2.5
2011-02-02T14:33:32.353Z
@Arman: Chandra didn't mean "find all matchings."  But for finding a max-weight matching of cardinality k, in the graph terminology, if you have an n-vertex graph G, you add n-2k extra vertices and edges between these n-2k vertices and the n vertices in G (with edge-weight all one, say).  Then, in any perfect matching of the new graph, n-2k vertices in G are matched with n new vertices, and 2k vertices in G are matched within G.  So a max-weight perfect matching in the new graph gives a max-weight matching of cardinality k in G.
Yoshio Okamoto
CC BY-SA 2.5
2011-02-02T16:22:07.977Z
Could you specify this as a linear programme (I haven't thought about that for even one second)? Anyway, without being mean, this seems like a good time to crack open a book on optimisation or operational research (branches of mathematics that deal with these sorts of problems), to get some ideas.
Marcin
CC BY-SA 2.5
2011-02-02T18:18:22.143Z
@Yoshio: I didn't know this trick, thanks.
Arman
CC BY-SA 2.5
2011-02-05T13:49:00.483Z
If you have a numerical penalty for unmatched vertices, then you can adapt the max-weight perfect matching algorithm to find the best possible matching with penalties, along the same lines as Yoshio explained above. Add a bunch of extra vertices to absorb unmatched vertices in G, put 0 weight on edges between the extra vertices, and put the penalty on edges between vertices in G and the extra vertices.
Peter Shor 
CC BY-SA 2.5
2011-02-05T13:52:27.657Z
The algorithm for finding the optimum matching (Edmond's algorithm) is quite intricate, and thus hard to program, but Arman has found an existing implementation, and it might not be too hard to adapt this (or maybe another existing implementation).
Peter Shor 
<ds.algorithms><matching>
Matching algorithm
Dónal
# Matching algorithm

(Asked by: username_0 on 2011-01-31)

I'm writing an application which divides a population of users into pairs for the purpose of performing a task together. Each user can specify various preferences about their partner, e.g.

gender
language
age
location (typically, within X miles/kilometers from where the user lives)

Ideally, I would like the user to be able to specify whether each of these preferences is a "nice to have" or a "must have", e.g. "I would prefer to be matched with a native English speaker, but I must not be matched with a female".
My objective is to maximise the overall average quality of the matches. For example, assume there are 4 users in the system, A, B, C, D. These users can be matched in 3 ways:

Option 1     Match Score
A-B           5
C-D           4
---
Average       4.5

Option 2     Match Score
A-C           2
B-D           3
---
Average       2.5

Option 3     Match Score
A-D           1
B-C           9
---
Average       5

So in this contrived example, the 3rd option would be chosen because it has the highest overall match quality, even though A and D are not very well matched at all.
Is there an algorithm that can help me to: 

calculate the "match scores" shown above
choose the pairings that will maximise the average match score (while respecting each user's absolute constraints)

It is not absolutely necessary that each user is matched, so given a choice between significantly lowering the overall quality of the matches, and leaving a few users without a match, I would choose the latter.
Obviously, I would like the algorithm that calculates the matches to complete as quickly as possible, because the number of users in the system could be quite large.
Finally, this system of computing match scores and maximizing the overall average is just a heurisitic I've come up with myself. If there's a much better way to calculate the pairings, please let me know.
Update
The problem I've described seems to be a similar to the stable marriage problem for which there is a well-known solution. However, in this  problem I do not require the chosen pairs to be stable. My goal is to choose the pairs so that the average "match score" is maximized

**Tags:** ds.algorithms, matching

> **Comments:**
> **username_1**: Welcome to CSTheory, @Don!  
> **username_2**: http://en.wikipedia.org/wiki/Hungarian_algorithm ?  
> **username_3**: Hungarian algorithm can be applied to bipartite graphs. I think Edmond's matching algorithm would be more convinient for this problem. for an implementation: http://www.xs4all.nl/~rjoris/maximummatching.html  
> **username_4**: If the objective function to maximize is the _sum_ of the score of each match, the problem is called “maximum weighted matching in general graphs” ([Wikipedia](http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm#Weighted_matching)).  If you really want to maximize the _average_ score of a match, then it is always the optimal to choose only one match (with the maximum score).  The problem is underspecified if you want something in between.  
> **username_5**: Tsuyoshi, it sounds like he wants a perfect matching (although it's not clear such a matching exists), in which case the sum and average are minimized the same way  
> **username_4**: @Suresh: My comment is based on the following part of the question: “It is not absolutely necessary that each user is matched, so given a choice between significantly lowering the overall quality of the matches, and leaving a few users without a match, I would choose the latter.”  
> **username_5**: @Tsuyoshi ah fair enough. that *does* leave it ill specified.  
> **username_6**: One option is to consider maximum weight matching among all matchings of a given cardinality k which should be also doable in polynomial time. Once you guess k the question of sum and average goes away and it may also be helpful to consider different values of k.  
> **username_3**: @Chandra: How do we find all matchings of a given cardinality k in polynomial time? Do you have any reference?  
> **username_7**: @username_3: Chandra didn't mean "find all matchings."  But for finding a max-weight matching of cardinality k, in the graph terminology, if you have an n-vertex graph G, you add n-2k extra vertices and edges between these n-2k vertices and the n vertices in G (with edge-weight all one, say).  Then, in any perfect matching of the new graph, n-2k vertices in G are matched with n new vertices, and 2k vertices in G are matched within G.  So a max-weight perfect matching in the new graph gives a max-weight matching of cardinality k in G.  
> **username_8**: Could you specify this as a linear programme (I haven't thought about that for even one second)? Anyway, without being mean, this seems like a good time to crack open a book on optimisation or operational research (branches of mathematics that deal with these sorts of problems), to get some ideas.  
> **username_3**: @Yoshio: I didn't know this trick, thanks.  
> **username_9**: If you have a numerical penalty for unmatched vertices, then you can adapt the max-weight perfect matching algorithm to find the best possible matching with penalties, along the same lines as Yoshio explained above. Add a bunch of extra vertices to absorb unmatched vertices in G, put 0 weight on edges between the extra vertices, and put the penalty on edges between vertices in G and the extra vertices.  
> **username_9**: The algorithm for finding the optimum matching (Edmond's algorithm) is quite intricate, and thus hard to program, but username_3 has found an existing implementation, and it might not be too hard to adapt this (or maybe another existing implementation).  

---

## 1 answers

### Answer by username_10 on 2011-02-05. Score: -2

You can fill sparse matrix vis match score between pairs . each row, column some person. And then you should select maximum on each row and maximum on each column if they are matched you should associate them.

It is not optimal algorithm. If you need optimal you should write dynamic program similar to one in Edit Distance.

> **Comments:**
> **username_9**: This isn't a deterministic algorithm. What do you do if the maximum on some row isn't the maximum on the corresponding column?  

---

